poj 3009 Curling 2.0 （dfs的应用）

 http://poj.org/problem?id=3009

（1）这是一个用球撞石头的游戏，撞到石头，石碎球停。在规定的10次抛球机会下，若求移动到终点就赢，否则算输了（出界直接算输）。

（2）每一次的深搜都有四个方向，每个方向要一直走，直到出现以下状况为止：

　　　　1）刚要抛球，被墙挡住了（该情况不能抛球）；

　　　　2)  出界；

　　　　3）到达终点；

　　　　4) 撞墙。

　　　　其中只有第四种情况需要进行深搜，其他情况均不需要。（虽然这很显然，但是案例

　　　　通不过的基本上就是因为这个，千万小心）。

（3）通过了所有案例，为什么还是WA？？小心，注意输入 n，m 顺序问题。题中所给的案例

　　 恰好与n，m 的顺序无关。。。这是挖好了陷阱等你呢。

（4）稍微注意： if(!n&&!m) break;

总的来说，这是一道不错的dfs入门题。

具体代码：

View Code #include<stdio.h> #include<string.h> #define Inf (1<<28) int n, m; int map[25][25]; int dir[4][2]={1,0,0,1,-1,0,0,-1}; int px, py, ans; int dfs(int x, int y, int depth) {int i, j, k;if(depth>10) return 0;for(i=0;i<4;i++){int tx=x, ty=y, ex, ey;int g=0;for(j=0;;j=1){ex=tx+dir[i][0];ey=ty+dir[i][1];if(!j&&map[ex][ey]==1) break; //靠墙，不能投if(ex<=0||ex>n||ey<=0|ey>m) break; //出界if(map[ex][ey]==3) //终点 {if(ans>depth) ans=depth;return 0;}if(map[ex][ey]==1) {g=1; break;}//撞墙tx=ex; ty=ey;//球还在滚动中 }if(g){map[ex][ey]=0;dfs(tx, ty, depth+1); //下一步，只有撞墙的才算一步map[ex][ey]=1;}}return 0; } int main() {int i, j, k;while(scanf("%d%d", &m, &n)!=EOF, n||m) //注意 n, m 的顺序 {for(i=1;i<=n;i++)for(j=1;j<=m;j++){scanf("%d", &map[i][j]);if(map[i][j]==2) {px=i;py=j;}}ans=Inf;dfs(px, py, 1);if(ans!=Inf) printf("%d\n", ans);else printf("-1\n");}return 0; }

 

 

 

转载于:https://www.cnblogs.com/tim11/archive/2012/08/18/2645715.html

总结

以上是生活随笔为你收集整理的poj 3009 Curling 2.0 （dfs的应用）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。