[数据结构与算法]张三玩冰壶：C++用DFS深度优先搜索解POJ_3009_Curling 2.0问题

POJ_3009_Curling 2.0

就不放英文题目了，去POJ搜题号就可以看到

简单理解一下题目：
张三去玩一种新出的冰壶项目，在一个棋盘一样的冰面上，他站在其中一格S上，从S点出发，有一些棋盘格有障碍物，他可以沿着上左下右四个方向运动，但是只有碰到障碍物才能停下来，而且碰到障碍物会停在运动方向上障碍物前面那个格子上，障碍物会消失，一个方向算一步，如果步数超过10或者不小心出界都算失败，问张三最短走几步能到终点G。

看一下输入：
一次性输入好几组数据，每一组开头是棋盘的横向距离和纵向距离（非常无奈我在这又弄混了），然后是棋盘格情况的输入，0代表可以走，1代表有障碍，2代表起点，3代表终点。输入用两个0结束。

看一下输出：
将每一组棋盘格到达终点的最短步数逐行输出，如果没有办法在10步以内到达就输出-1。

简单分析：
用DFS深度优先搜索的思想，从起点四个方向循环，某个方向遇到障碍物停下来，将障碍物解除，下一步就从当前位置继续四个方向的dfs搜索，然后将障碍物还原，返回到上一步进行其他方向的搜索。初始设置一个记录最小步数的全局变量并设一个很大的值，每次通过一种新路径到达终点时用当前步数与最小步数比较，如果当前步数更小就更新最小步数，最终输出最小步数。如果最终最小步数还是那个很大的值，说明这个棋盘格张三没法在十步以内到达终点。

AC代码：

#include<iostream>

using namespace std;

int w, h;
int field[25][25];//输入字符数组
int sx, sy, gx, gy;//起点和终点的横纵坐标
int result[102];//结果存放在这个数组中
int dx[4] = { 0,-1,0,1 }, dy[4] = { 1,0,-1,0 };//上左下右四个方向
int minstep = 100000;//记录最小步数

void dfs(int x,int y,int step)//x与y表示当前位置，step表示当前已经走过的步数
{
	if (step > 10)
		return;
	if (field[x][y] == 3)
	{
		minstep = min(minstep, step);
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int nx = x, ny = y, nex = x + dx[i], ney = y + dy[i];//nx、ny表示当前位置，nex、ney表示该方向上下一个位置
		while (nex >= 0 && nex < w && ney >= 0 && ney < h && field[nex][ney]!=1)//在此方向上再移动一格可以走且没有出界的情况下
		{
			nx = nx + dx[i], ny = ny + dy[i];//把当前位置往前走一格

			if (field[nx][ny] == 3)
			{
				minstep = min(minstep, step);
				return;
			}

			nex = nx + dx[i], ney = ny + dy[i];//更新下一格

			if (nex >= w || nex < 0 || ney >= h || ney < 0)
			{
				break;
			}

			if (field[nex][ney] == 1)
			{
				field[nex][ney] = 0;//将障碍物清除
				dfs(nx, ny, step + 1);
				field[nex][ney] = 1;//将障碍物还原
			}
		}
	}
}

int solve()
{
	minstep = 100000;
	dfs(sx, sy, 1);
	return minstep;
}

int main()
{
	int k = 0;
	for(k=0;;k++)
	{
		cin >> h >> w;
		if (w == 0 && h == 0)
			break;
		for (int i = 0; i < w; i++)
		{
			for (int j = 0; j < h; j++)
			{
				cin >> field[i][j];
				if (field[i][j] == 2)
				{
					sx = i;
					sy = j;
				}
				if (field[i][j] == 3)
				{
					gx = i;
					gy = j;
				}
			}
		}
		result[k]=solve();
		if (result[k] == 100000)
			result[k] = -1;

	}
	for (int i = 0; i < k; i++)
	{
		cout << result[i] << endl;
	}
	return 0;
}

/* 
2 1
3 2
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1
6 1
1 1 2 1 1 3
6 1
1 0 2 1 1 3
12 1
2 0 1 1 1 1 1 1 1 1 1 3
13 1
2 0 1 1 1 1 1 1 1 1 1 1 3
0 0
*/

做题心得：
这道DFS题，我一开始没有每次dfs完后将障碍物还原，导致无法做出，另外h和w在判断是否出界的时候对应x和y我还搞反了，以后一定要看清楚了再敲代码。

最后，感谢查阅，欢迎批评指正~