poj3009 Curling 2.0

发布时间:2014-10-22 19:56:11编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj3009 Curling 2.0",主要涉及到poj3009 Curling 2.0方面的内容,对于poj3009 Curling 2.0感兴趣的同学可以参考一下。

链接:http://poj.org/problem?id=3009 总算是磕磕盼盼的自己写了一题。 一开始只用了一个全局变量move,显然不行,后来加了step才行得通。     #include<iostream> #define MAXW 25 #define MAXH 25 using namespace std; int map[MAXH][MAXW]; int w,h; int move,min_move;//move记录成功的一趟的移动次数,min_move则是记录最小的移动次数 void DFS(int i,int j,int step) { if(step>10)return;//剪枝,移动次数大于10,直接放弃 int m=i,n=j; //记录开始位置的坐标 if(map[i+1][j]!=1)//如果冰壶的邻近位置就是积木,则不可移动 { while(i<h&&map[i+1][j]==0)//如果冰壶前方一直为0,则可一直移动,直到遇到积木1或者目的3 i++; if(map[i+1][j]==3&&i<h)//如果遇到目的3,则此次过程结束 { move=step; //记录移动次数 if(move<min_move) //记录最小的移动次数 min_move=move; return; } if(i<h) //遇到积木1 { map[i+1][j]=0; //积木被撞碎,变为0 DFS(i,j,step+1); //新的起点 map[i+1][j]=1; //回朔,积木还原 } } i=m; //起始坐标还原 j=n; if(map[i-1][j]!=1) { while(i>1&&map[i-1][j]==0) i--; if(map[i-1][j]==3&&i>1) { move=step; if(move<min_move) min_move=move; return; } if(i>1) { map[i-1][j]=0; DFS(i,j,step+1); map[i-1][j]=1; } } i=m; j=n; if(map[i][j-1]!=1) { while(j>1&&map[i][j-1]==0) j--; if(map[i][j-1]==3&&j>1) { move=step; if(move<min_move) min_move=move; return; } if(j>1) { map[i][j-1]=0; DFS(i,j,step+1); map[i][j-1]=1; } } i=m; j=n; if(map[i][j+1]!=1) { while(j<w&&map[i][j+1]==0) j++; if(map[i][j+1]==3&&j<w) { move=step; if(move<min_move) min_move=move; return; } if(j<w) { map[i][j+1]=0; DFS(i,j,step+1); map[i][j+1]=1; } } return; } int main() { int i,j,num; int si,sj; while(cin>>w>>h&&w&&h) { for(i=1;i<=h;i++) for(j=1;j<=w;j++) { cin>>num; map[i][j]=num; if(num==2) { si=i; sj=j; map[i][j]=0; //初始位置等价于0 } } move=-1; min_move=11; DFS(si,sj,1); cout<<((min_move==11)?-1:min_move)<<endl; } return 0; }  


上一篇:初入项目,坑自己的习惯,小结
下一篇:T-SQL如何將YYYYMMDDHHmmssnnn轉換為datetime

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款