POJ 3009 Curling 2.0 《挑战程序设计竞赛(第2版)》练习题答案

2.1 最基础的“穷竭搜索” 深度优先搜索

POJ 3009 Curling 2.0

扔石头，上下左右四个方向如果某一个方向紧挨着block就不能扔这个方向，否则碰到block停住，block消失，再次四个方向扔。DFS老一套，不过一定要注意判断紧挨着的情况。超过最小步数剪枝也是个很有意思的技巧。

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int w, h;
int map[32][32];
int sx, sy;
int min_step;
const int direction[4][2] = {
	{ -1, 0 },
	{ 1, 0 },
	{ 0, -1 },
	{ 0, 1 },
};

void dfs(const int& x, const int& y, int step)
{
	if (step >= 10 || step > min_step)
	{
		return;
	}
	
	for (int i = 0; i < 4; ++i)
	{
		int nx = x;
		int ny = y;
		// 让石头往固定的方向一直飞
		while(nx >= 0 && nx < w && ny >= 0 && ny < h)
		{
			switch (map[nx][ny])
			{
				case 0:
				{
				    // 继续飞
					nx += direction[i][0];
					ny += direction[i][1];
				}break;
				case 3:
				{
					// 到家了
					if (step + 1 < min_step)
					{
						min_step = step + 1;
					}
					nx = -1;
				}break;
				case 1:
				{

					// 撞到了block
					if (!(nx - direction[i][0] == x && ny - direction[i][1] == y))
					{
						// 中间有空地，不是紧挨着block
						// 石头消失
						map[nx][ny] = 0;
						// 后退一步扔石头
						dfs(nx - direction[i][0], ny - direction[i][1], step + 1);
						// 复原地图，供下一个方向尝试
						map[nx][ny] = 1;
					}
					// 开始下一个方向
					nx = -1;
				}break;
				default:
					break;
			}
		}
		
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	
	while (cin >> w >> h, w != 0)
	{
		for (int i = 0; i < h; ++i)
		{
			for (int j = 0; j < w; ++j)
			{
				cin >> map[j][i];
			}
		}
		for (int i = 0; i < h; ++i)
		{
			for (int j = 0; j < w; ++j)
			{
				if (2 == map[j][i])
				{
					sx = j;
					sy = i;
					i = h;
					break;
				}
			}
		}

		map[sx][sy] = 0;
		min_step = 11;
		dfs(sx, sy, 0);
		if (min_step > 10)
		{
			min_step = -1;
		}
		cout << min_step << endl;
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3009 Curling 2.0 《挑战程序设计竞赛(第2版)》练习题答案