原题目如下：
今年的奥运会之后，在行星mm-21上冰壶越来越受欢迎。但是规则和我们的有点不同。这个游戏是在一个冰游戏板上玩的，上面有一个正方形网格。他们只用一块石头。游戏的目的是让石子从起点到终点，并且移动的次数最小
图1显示了一个游戏板的例子。一些正方形格子可能被砖块占据。有两个特殊的格子，起始点和目标点，这是不占用块。（这两个方块是不同的）一旦石头开始移动就不会停下，除非它击中砖块块。为了使石头到达终点，你可以通过让石块击中墙壁或者砖块来停下。
图1：例子（S：开始，G：目标）
石头的运动遵循以下规则：
开始时，石头静止起点广场上。
石头的运动仅限于x和y方向。禁止对角线移动。
当石头静止时，你可以让他向任意方向移动，除非它移动的方向上有砖块（图2（a））。
一旦抛出，石头不断向同一方向移动，直到下列事件之一发生：
石头击中砖块（图2（b），（c））。.
石头停在他击中的砖块之前
被击中的砖块消失
石块飞出游戏板之外。
游戏结束的条件
到达目标点
石头停在目标点游戏成功
不能在十步之内到达目标点则返回失败。
Fig. 2: Stone movements
通过这些规则我们想知道，石头是否能够到达目标点和最少移动次数
初始配置如图1所示，石头从开始到目标需要4次移动。路线如图3所示（a）。注意当石头到达目标时，游戏版的配置如图3（b）改变。
图3：图1的解决方案和解决之后的结果。
输入是一组数据。输入结束标志为两个0。数据组的数量不超过100。
每个数据集如下展示
板的宽度（w）和高度（h）
游戏版的第一行
...
游戏版的h-th行
版的宽和高满足: 2 <= w <= 20, 1 <= h <= 20.
每行由一个空格分隔的十进制数字组成。该数字描述相应的格子的状态。
0 空
1 砖块
2 开始点
3 目标点
图. D-1数据如下:
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
Output
对于每个数据，打印一个十进制整数的行，表示从开始到目标的路径的最小移动次数。如果没有这样的路线，打印- 1。每个行不应该有这个数字以外的任何字符。
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
Sample Output
1
4
-1
4
10
-1
解题思路：
首先，这道题也是一道非常经典的dfs题，只不过它跟POJ 2386等类似的题相比，POJ 2386 dfs的是图中的一个数（字符），而这道题dfs的是图中的一行，也就是当这道题的冰壶处于静止状态时开始进行dfs搜索，在搜索时只能按照一个方向进行移动，当冰壶出界或者说到达终点时游戏结束，否则如果移动到了墙上，则冰壶再次处于静止状态。此时我们应该再一次进行dfs搜索。这道题如果看懂题目之后，其实很容易就能想出思路，但是，这道题由于要求很多，因此有很多坑需要注意。我也是debug了很多次，从网上看了AC代码之后才发现自身的问题。
这道题的注意事项：
1. 这道题先输入的是宽度，再输入的是高度！这一点请一定注意。
2. 冰壶进行移动的次数为10步以内（包括第10步），按照本题的思路来讲，进行到了第10次之后，如果还没有到终点，则在第11次dfs时，游戏就结束了。（return)
3. 这道题用到了回溯算法，实际上当你每次进行dfs搜索时都是冰壶碰到墙上的情况（第一次除外)，因为冰壶碰到墙上，墙会消失。因此，当你某一次dfs搜索完之后进行回溯到上一次dfs的状态时,请一定要将消失的墙给还原回来!
4. 起点不算碰撞物，所以说从找到起点开始进行dfs之前，请将起点置为空地
5.这也是我WA的原因，请一定注意在进行规则判断时，一定要将判断边界放在第一位，其次是碰到墙或者到达终点。因为测试数据的原因，可能会有上一次的测试数据影响到这一次测试数据的情况。
例如：
上一次测试数据为：
6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 3 0
1 0 0 0 0 1
0 1 1 1 1 1
如果说这一次的测试数据你获得了正确的结果，请不要高兴太早，如果紧接着下一次的测试数据为：
7 3
1 1 2 1 3 1 1
1 1 0 0 0 0 1
1 1 1 0 1 0 1
那么，可能就会出现，当你的冰壶移动到第二行第六列时，如果你先将判断终点或者说碰到墙壁放在了第一位，那么当你的冰壶进行dfs搜索向下遍历时时很可能就遍历到了上一次测试数据中的第四行中的第五列中的终点。从而导致了结果的错误！所以这是一个非常不好看出的问题，如果说想解决这个问题的话，请一定要将判断边界的条件放在第一位！或者说每次测试实例之后，请一定要将清空代表图的二维数组!
请注意，上面所举的例子可能会出现很多不合理的问题，因此仅仅作为讲题使用。
代码如下：
#include <iostream>
#include <cstdio>
using namespace std;
int MIN = 11;
int w, h;
int Graph[100][100];
int ex, ey;
int Count = 0;
void dfs(int x, int y, int Count);
void dfs(int x, int y, int Count)
{
int movex=x, movey=y;
int i, j;
Count++;
if (Count > 10)
{
return;
}
for (i = -1; i <= 1; i++)
{
for (j = -1; j <= 1; j++)
{
if (i == 0 || j == 0)
{
if ( x+i >= 0 && x+i < h && y+j >= 0 && y+j < w && Graph[x+i][y+j] != 1 && (i!=0 || j !=0))
{
while (true)
{
movex = movex + i;
movey = movey + j;
if (movex < 0 || movex >= h || movey < 0 || movey >= w)
{
break;
}
else if (Graph[movex][movey] == 1)
{
Graph[movex][movey] = 0;
movex = movex - i;
movey = movey - j;
dfs(movex, movey, Count);
Graph[movex + i][movey + j] = 1;
break;
}
else if (movex == ex && movey == ey)
{
if (Count < MIN)
{
MIN = Count;
}
return;
}
}
movex = x;
movey = y;
}
}
}
}
}
int main()
{
int i, j,x;
while (scanf("%d %d", &w, &h) != EOF)
{
if (w == 0 && h == 0)
{
return 0;
}
else
{
for (i = 0; i < h; i++)
{
for (j = 0; j < w; j++)
{
cin >> x;
Graph[i][j] = x;
if (Graph[i][j] == 3)
{
ex = i;
ey = j;
}
}
}
for (i = 0; i < h; i++)
{
for (j = 0; j < w; j++)
{
if (Graph[i][j] == 2)
{
Graph[i][j] = 0;
dfs(i, j, Count);
}
}
}
if (MIN == 11)
{
printf("-1\n");
}
else
{
printf("%d\n", MIN);
}
Count = 0;
MIN = 11;
}
}
}
POJ 3009 Curling 2.0