修改了两天。搜索的题目好理解，但是要多练练手感啊......
POJ 3009 冰壶游戏 ：http://poj.org/problem?id=3009
题意： 给出 列、行
给出矩阵。 通路为0，墙壁为1，起点为2，终点为3
将冰壶起点击出，不碰到墙壁或出界 不会停止。也就是直线运动。
冰壶撞到墙壁后，在墙壁前面停下！！并且墙壁会碎裂！！
问最少击打次数，使得冰壶经过或停留终点位置。
题目限定，最少击打数必须小于10。 若无解输出-1 。
Vjudge上面没图，洋文没看通透，结果不知道冰壶撞到墙壁墙壁会碎裂。愚蠢的理所让然的写了BFS，结果样例都过不了。
看了百度，才发现墙壁会碎，只能用DFS了....
DFS思路：
每一层递归就是一个击打点。
击打数超过10就结束；
直接对四个方向进行模拟滑行。
滑出界就停止；滑到终点更新最小值并结束；到墙壁就停下，墙壁碎裂标记，从墙壁前递归下个击打点并之后回溯。
最后输出最小值（起始为无穷大）。若为无穷大则输出-1.
值得注意的是题目隐含点： 击打点面朝墙壁，则不可直接击打。 也就是说，冰壶需要至少一格空位滑行才能撞碎墙壁。否则要处理跳过。
上DFS代码：
#include"cstdio" #include"queue" #include"cstring" #include"algorithm" using namespace std; #define inf 999999999 int book[21][21]; int n,m; int pos[4][2]={0,1,0,-1,1,0,-1,0}; int sx,sy,gx,gy,ans; int pan(int i,int j) { if(i<0||i>=n||j<0||j>=m)return 0; return 1; } void dfs(int x,int y,int step) { if(step>10)return; for(int i=0;i<4;i++) { int &dx=pos[i][0]; int &dy=pos[i][1]; int rx=x,ry=y; if(book[rx+dx][ry+dy]==1)continue; while(pan(rx+dx,ry+dy)) { if(book[rx+dx][ry+dy]==0) {rx+=dx; ry+=dy; } else if(gx==rx+dx&&gy==ry+dy) { ans=min(ans,step); break; } else {book[rx+dx][ry+dy]=0;dfs(rx,ry,step+1);book[rx+dx][ry+dy]=1;break;} } } } int main() { while(~scanf("%d%d",&m,&n)&&n&&m) { ans=inf; memset(book,0,sizeof book); for(int i=0;i<n;i++) for(int j=0;j<m;j++) { scanf("%d",&book[i][j]); if(book[i][j]==2) { sx=i;sy=j; book[i][j]=0; } else if(book[i][j]==3) {gx=i;gy=j;} } dfs(sx,sy,1); if(ans==inf)printf("-1\n"); else printf("%d\n",ans); } return 0; }
