1.原题：http://poj.org/problem?id=3009。题意是冰壶游戏，给定若干组的地图，W表示宽度（列数）H表示高度（行数）。然后接下来的H行W列就是地图数据。0表示没有障碍 1表示障碍 2表示起点 3表示终点。程序的目的是给定一个起点和一个终点，求出满足下列规则的最小的移动数目。
规则：
A.每次冰壶碰到障碍，可以用捆棍子向上下左右移动，并且冰壶的轨迹沿推出的方向。
B.如果冰壶出界、没有路可走或者是10次移动操作内不能到达终点，那么游戏失败输出-1。否则需要求出最小的移动操作
C.冰壶碰到障碍的话，障碍会消失。
2.思路：可以用DFS相四个方向探测，然后临时标记一下起始点，注意我们要沿着方向走，所以需要一个循环一直探测到没有障碍的位置（如果是之前访问的位置没关系，那肯定会失败。）。如果探测打那个点是障碍，那么临时移除他，然后dfs，深度+1；如果是终点，比较最小值；如果是普通的点，就直接dfs，深度+1。递归的基线条件就是depth（深度）>10（从1开始的）
3.代码：
#include <cstdio>
#include <vector>
#include <algorithm>
enum Node {
NO = 0, BLOCK, START, GOAL
};
const int MAX_W = 20;
const int MAX_H = 20;
int map[MAX_W][MAX_H];
//int flag[MAX_W][MAX_H];
int res[100] = { 0 };
int w, h;
const int limit = 10;
int minopt = limit + 1;
int dir[4][2] = { { 0,-1 },{ -1,0 },{ 0,1 },{ 1,0 } };//四个方向
bool dfs(int depth, int x, int y)
{
if (depth >limit)
{
//fail the game
return false;
}
int dx, dy;
for (int i = 0; i<4; ++i)
{
dx = x + dir[i][0];
dy = y + dir[i][1];
if (dx >= 0 && dx <h && dy >= 0 && dy <w && map[dx][dy] !=BLOCK)
{
//合法的点 那么需要项这个方向递增移动到下一个组块之前 然后进行dfs
int nx = dx, ny = dy;
for (; nx >= 0 && nx <h && ny >= 0 && ny <w && (map[nx][ny] == NO || map[nx][ny]==START); nx = nx + dir[i][0], ny = ny + dir[i][1])
;
if (nx <0 || nx >= h || ny <0 || ny >= w)
continue;
//if (flag[nx][ny] == 1)//这个根本没什么用 因为冰壶会把之前的进过的位置全部撞开 所以我只需要讨论下一步是否出界或者是撞到块的情况
//continue;
if (map[nx][ny] == GOAL)
{
minopt = std::min(minopt, depth);
continue;
}
if (map[nx][ny] == BLOCK)
{
//HIT IT REMOVE;
map[nx][ny] = NO;
//flag[x][y] = 1;
dfs(depth + 1, nx - dir[i][0], ny - dir[i][1]);
//flag[x][y] = 0;
map[nx][ny] = BLOCK;
}
else
{
//flag[x][y] = 1;
dfs(depth + 1, nx - dir[i][0], ny - dir[i][1]);
//flag[x][y] = 0;
}
}
}
}
int main()
{
int r = 0;
while (~scanf("%d %d", &w, &h) && w != 0 && h != 0)
{
int bx, by;
for (int i = 0; i<h; ++i)
{
for (int j = 0; j<w; ++j)
{
scanf("%d", &map[i][j]);
if (map[i][j] == START)
bx = i, by = j;
}
}
//地图准备完毕了
dfs(1, bx, by);
if (minopt == limit + 1)
{
res[r++] = -1;
}
else
{
res[r++] = minopt;
}
minopt = limit + 1;
}
for (int i = 0; i<r; ++i)
{
if (res[i] != 0)
printf("%d\n", res[i]);
}
return 0;
}