https://vjudge.net/problem/POJ-3009
在 MM-21 星球上，今年的奥运会之后，冰壶运动开始流行起来。但规则与我们的有些不同。冰壶比赛是在一块冰板上进行的，冰板上标有方形网眼。
他们只使用一块石头。游戏的目的是用最少的步数将石头从起点引向终点。
图 1 显示了游戏棋盘的一个示例。一些方格可能被积木占据。有两个特殊的方格，即起点和目标方格，这两个方格没有积木。(这两个方格是不同的。）
一旦棋子开始移动，它就会一直走下去，直到碰到一个积木为止。为了让石子到达目标，你可能需要让石子停下来，撞上一个木块，然后再扔一次。
图 1：棋盘示例（S：起点，G：终点）
石子的移动遵循以下规则：
开始时，石子静止在起` 点方格。
石子的移动仅限于 x 和 y 方向。禁止对角线移动。
当石块静止不动时，您可以通过投掷使其移动。您可以将它扔向任何方向，除非它立即被挡住（图 2(a)）。
投掷后，石子会一直向同一方向移动，直到出现以下情况之一：
石子击中一个木块（图 2(b)、(c)）。
石块停在被击中石块旁边的方格。
木块消失。
棋子离开棋盘。
游戏以失败告终。
石子到达目标方格。
石子停在目标方格，游戏以成功结束。
一局游戏中投掷石块的次数不能超过 10 次。如果石子在 10 次移动中没有到达目标位置，则游戏以失败告终。
图 2：石子移动
根据规则，我们想知道石头在开始时是否能到达目标，如果能，则需要最少的移动次数。
按照图 1 所示的初始配置，需要走 4 步棋才能将石子从起点带到终点。路线如图 3(a) 所示。注意，当棋子到达终点时，棋盘的配置发生了变化，如图 3(b)所示。
输入是一系列数据集。输入结束时，会出现一行包含两个 0 的空格。数据集的数量永远不会超过 100 个。
每个数据集的格式如下。
电路板的宽度（=w）和高度（=h）
棋盘第一行
...
棋盘的第 h 行
黑板的宽度和高度满足以下条件： 2 <= w <= 20，1 <= h <= 20。
每行由 w 个十进制数字组成，以空格分隔。数字描述了相应方格的状态。
0 空方格
1 块
2 开始位置
3 目标位置
The dataset for Fig. D-1 is as follows:
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
输出
对于每个数据集，打印一行十进制整数，表示从起点到目标的最小移动次数。如果没有这样的路线，则打印-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
14 6
0 0 1 0 0 0 0 1 1 0 1 1 1 0
0 0 1 0 1 0 1 1 1 1 1 1 1 1
1 1 0 2 1 1 0 0 1 0 0 0 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 0
1 0 1 1 1 0 1 1 0 1 1 0 0 0
1 0 1 0 0 1 0 0 1 0 0 0 0 3
4 8
0 1 0 0
0 0 0 0
1 0 0 1
0 0 0 0
0 0 0 0
3 0 1 0
1 0 1 0
1 0 0 2
0 0
输出
1
4
-1
4
10
-1
根据题意
本来可以考虑使用BFS 查看10回合以内覆盖的范围。
但是每次移动后，碰到冰壁会损坏墙壁，状态是变化的。BFS不方便记录。
所以 考虑DFS10回合内的所有移动，更加方便。
注意 通过目标位置即可 不用停留在目标位置上
代码如下
#include <iostream>
#include <queue>
#include <cstring>
//https://vjudge.net/problem/POJ-3009
using namespace std;
const int N = 22;
int gra[N][N];
int w, h, startx, starty;
int ans = 0x3f3f3f3f;
void dfs(int x, int y, int step);
void change(int x, int y, int addx, int addy, int step) {
int newx = x + addx; int newy = y + addy;
if (newx >= 0 && newx < h && newy >= 0 && newy < w && gra[newx][newy] == 1) {
//不能往这个方向移动
return;
}
if (newx < 0 || newx >= h || newy < 0 || newy >= w) {
//滑出街 不能移动
return;
}
x += addx, y += addy;
//开始滑动
while (x >= 0 && x < h && y >= 0 && y < w) {
if (gra[x][y] == 3) {
ans = min(step+1, ans);
return;
}
else if (gra[x][y] == 1) {
gra[x][y] = 0;
dfs(x-addx, y-addy, step + 1);
gra[x][y] = 1; return;
}
x += addx, y += addy;
}
}
void dfs(int x, int y, int step) {
//向四个方向滑动
if (step > 10) return;
change(x, y, 0, 1, step);
change(x, y, 0, -1, step);
change(x, y, 1, 0, step);
change(x, y, -1, 0, step);
return ;
}
void solve() {
ans = 0x3f3f3f3f;
dfs(startx,starty,0);
if (ans > 10) ans = -1;
cout << ans << endl;
}
int main() {
while (cin >> w >> h) {
if (w == 0 && h == 0)break;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> gra[i][j];
if (gra[i][j] == 2) {
startx = i; starty = j;
}
}
}
solve();
}
return 0;
}