Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
开始用bfs写,因为棋盘的状态会改变,代码不好写,还超时了。改用dfs看起来确实舒服很多。#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <queue> using namespace std; const int N=25; int planet[N][N]; int dir[4][2] = {{0,1},{-1,0}, {1,0}, {0,-1}}; int n,m, sx,sy,ex,ey, ans; void dfs(int x, int y, int step){ if(step>=10) return; for(int i=0; i<4; i++){ int nx = x; int ny = y; int bfirst = 1; while(1){ nx += dir[i][0]; ny += dir[i][1]; if(!(nx>=0 && nx<m && ny>=0 && ny<n)) break; if(planet[nx][ny] == 1){ if(bfirst) { break; } else{ int tx = nx-dir[i][0]; int ty = ny-dir[i][1]; planet[nx][ny]=0; dfs(tx, ty, step+1); planet[nx][ny]=1; break; } } else if(planet[nx][ny] == 3){ int tmp = step+1; if(tmp<ans){ ans=tmp; } break; } if(bfirst) bfirst=0; } } } int main(){ //freopen ("in.txt" , "r" , stdin); //freopen ("out.txt" , "w" , stdout); while(1){ cin>>n>>m; if(n==0 && m==0) break; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ cin>>planet[i][j]; if(planet[i][j] == 2) {sx=i;sy=j;} if(planet[i][j] == 3) {ex=i;ey=j;} } } ans = 20; dfs(sx, sy, 0); if(ans>10) ans=-1; cout<<ans<<endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator