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 关键还是 方向的确定 一次过 看我代码#include <iostream> #include <cstring> #include <queue> #include <cstdio> #define MAX 50 using namespace std; struct point { int x , y; int step; }; int visit[MAX][MAX]; char maze[MAX][MAX]; int mov_left[4][2] = {{0,-1},{1,0},{0,1},{-1,0}} ; // 靠左走 int mov_righ[4][2] = {{0,1},{1,0},{0,-1},{-1,0}} ; // 靠右走 int d1 , d2 ; int start[2]; int finish[2]; int w , h ; int dfs(int x,int y,int d,int move[][2]) { int step ,temp , tx , ty ; if(x == finish[0] && y == finish[1]) return 1 ; for(int i = 0; i < 4 ; i++) { temp = (d + i) % 4 ; tx = x + move[temp][1] ; ty = y + move[temp][0] ; if(tx>=0 && tx<h && ty>=0 && ty<w && !visit[tx][ty]) break ; } step = dfs(tx,ty,(temp + 3)%4,move) + 1; return step; } int bfs() { memset(visit,0,sizeof(visit)); queue<point> Q; point p; p.x = start[0] ; p.y = start[1] ; p.step = 1; visit[p.x][p.y] = 1 ; Q.push(p); while(!Q.empty()) { p = Q.front(); Q.pop(); if(p.x == finish[0] && p.y == finish[1]) return p.step ; for(int i = 0 ; i < 4 ; i ++) { point temp ; temp.x = p.x + mov_left[i][1] ; temp.y = p.y + mov_left[i][0] ; if(temp.x>=0 && temp.x<h && temp.y>=0 && temp.y<w && maze[temp.x][temp.y]!='#' && !visit[temp.x][temp.y]) { visit[temp.x][temp.y] = 1; temp.step = p.step + 1 ; Q.push(temp) ; } } } return 0; } int main() { //freopen("in.txt","r",stdin); int n; cin>>n; while(n--) { int i , j ; cin>>w>>h; memset(visit,0,sizeof(visit)); for(i = 0; i < h; i++) { for(j = 0; j < w; j++) { cin>>maze[i][j]; if(maze[i][j] == '#') { visit[i][j] = 1; } if(maze[i][j] == 'S') { start[0] = i ; start[1] = j ; } if(maze[i][j] == 'E') { finish[0] = i ; finish[1] = j ; } } } if(start[0] == 0) { d1 = 1 ; d2 = 1 ; } else if(start[0] == h-1) { d1 = 3 ; d2 = 3 ; } else if(start[0] == w-1) { d1 = 2 ; d2 = 0 ; } else { d1 = 0 ; d2 = 2 ; } cout<<dfs(start[0],start[1],d1,mov_left)<<" "; cout<<dfs(start[0],start[1],d2,mov_righ)<<" "; cout<<bfs()<<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