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 |
dfs+bfs 120行#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <queue> using namespace std; const int N=50; char maze[N][N]; int visit[N*N]; int deep[N*N]; int ans,anss, sx,sy,ex,ey,m,n; int dir_dfs[2][4][4][2]= {{{{0,-1}, {-1,0}, {0,1}, {1,0}}, {{-1,0}, {0,1}, {1,0}, {0,-1}}, {{0,1}, {1,0}, {0,-1}, {-1,0}}, {{1,0}, {0,-1}, {-1,0}, {0,1}}}, {{{0,1}, {-1,0}, {0,-1}, {1,0}}, {{1,0}, {0,1}, {-1,0}, {0,-1}}, {{0,-1}, {1,0}, {0,1}, {-1,0}}, {{-1,0}, {0,-1}, {1,0}, {0,1}}}}; int dir_bfs[4][2] = {{0,-1}, {-1,0}, {0,1}, {1,0}}; //d:当前方向 void dfs(int x, int y, int d, int step, int lr){ if(x==ex && y==ey){ ans = step; return; } for(int i=0; i<4; i++){ int nx = x+dir_dfs[lr][d][i][0]; int ny = y+dir_dfs[lr][d][i][1]; if(!(nx>=0 && nx<m && ny>=0 && ny<n)) continue; if(maze[nx][ny] == '#') continue; if(lr==0){ dfs(nx, ny, (d+i+3)%4, step+1, lr); }else{ if(i==0 || i==2) dfs(nx, ny, (d+i+1)%4, step+1, lr); else dfs(nx, ny, (d+i+3)%4, step+1, lr); } if(ans) return; } } void bfs(){ memset(visit, 0, sizeof(visit)); memset(visit, 0, sizeof(deep)); queue<int> q; while(!q.empty()) q.pop(); int sxy = sx*n+sy; q.push(sxy); visit[sxy]=1; deep[sxy]=1; while(!q.empty()){ int t = q.front(); q.pop(); int x = t/n; int y = t%n; for(int i=0; i<4; i++){ int nx = x+dir_bfs[i][0]; int ny = y+dir_bfs[i][1]; int nxy = nx*n+ny; if(!(nx>=0 && nx<m && ny>=0 && ny<n)) continue; if(maze[nx][ny] == '#' || visit[nxy]) continue; if(nx == ex && ny == ey){ anss = deep[t]+1; return; } visit[nxy]=1; deep[nxy] = deep[t]+1; q.push(nxy); } } } int main(){ //freopen ("in.txt" , "r" , stdin); //freopen ("out.txt" , "w" , stdout); int icase; cin>>icase; while(icase--){ cin>>n>>m; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ cin>>maze[i][j]; if(maze[i][j] == 'S') {sx=i;sy=j;} if(maze[i][j] == 'E') {ex=i;ey=j;} } } ans=0; dfs(sx,sy,0,1,0); cout<<ans<<" "; ans=0; dfs(sx,sy,0,1,1); cout<<ans<<" "; anss=0; bfs(); cout<<anss<<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