首页 > 代码库 > POJ3009 Curling 2.0(DFS)
POJ3009 Curling 2.0(DFS)
迷宫问题求最短路。略有不同的是如果不碰到石头的话会沿着一个方向一直前进,出界就算输了。碰到石头,前方石头会消失,冰壶停在原地。把这个当作状态的转移。DFS可以求出其最小操作数。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<vector> #include<cmath> #define ll __int64 #define INF 0x3f3f3f using namespace std; int n,m; int ex,ey; int Min; int dir[4][2]= {{1,0},{0,1},{0,-1},{-1,0}}; int map[25][25]; void dfs(int x,int y,int count) { if(count>10) return; for(int i=0; i<4; i++) { int move_ok=0; int xx=x,yy=y; if(map[x+dir[i][0]][y+dir[i][1]]==1) continue; while(true) { xx=xx+dir[i][0]; yy=yy+dir[i][1]; if(xx<0||xx>=n||yy<0||yy>=m) break; if(map[xx][yy]==1) { move_ok=1; break; } if(map[xx][yy]==3) { if(Min>count) { Min=count; break; } } } if(move_ok) { map[xx][yy]=0; dfs(xx-dir[i][0],yy-dir[i][1],count+1); map[xx][yy]=1; } } } int main() { //freopen("d:\\test.txt","r",stdin); int sx,sy; while(cin>>m>>n) { if(m==0&&n==0) break; memset(map,0,sizeof(map)); for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>map[i][j]; if(map[i][j]==2) { sx=i; sy=j; } } } Min=11; dfs(sx,sy,1); if(Min>10) cout<<"-1"<<endl; else cout<<Min<<endl; } return 0; }
POJ3009 Curling 2.0(DFS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。