題意：有一個W*H的map，‘#’表示障礙，'.'表示空地，'S'表示起點，'E'表示終點，且保證起點與終點各有一個。
分別輸出左轉優先，右轉優先以及最短的S到E的步數。。
思路：顯然左轉優先與右轉優先dfs，最短路徑bfs。
我定義的方向是 上右下左 分別為 0 1 2 3.
那麼左轉可表示為 d = (d+3)%4，右轉可表示為 d = (d+1)%4.
左轉優先時先右轉，然後順時針dfs;右轉優先時先左轉然後逆時針dfs。
最後，右轉優先從S到E相當於左轉優先從E到S，所以右轉是可以轉化為左轉，一個dfs即可。
#include#include #include #include using namespace std; int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; // 0 1 2 3 對應 上右下左 struct node { int x,y; int step; }; int n,m; char map[50][50]; queue que; int dfs(int x, int y,int ex, int ey,int d, int step) { if(x == ex && y == ey) return step; d = (d+3)%4; //優先左轉 int xx = x+dir[d][0]; int yy = y+dir[d][1]; while( map[xx][yy] == '#') //順時針旋轉直到可以走為止 { d = (d+1)%4; xx = x+dir[d][0]; yy = y+dir[d][1]; } return dfs(xx,yy,ex,ey,d,step+1); } int bfs(int sx,int sy,int ex,int ey) { int vis[50][50]; memset(vis,0,sizeof(vis)); while(!que.empty()) que.pop(); vis[sx][sy] = 1; que.push( (struct node) {sx,sy,1}); while(!que.empty()) { struct node u = que.front(); que.pop(); if(u.x == ex && u.y == ey) return u.step; for(int d = 0; d < 4; d++) { int x = u.x+dir[d][0]; int y = u.y+dir[d][1]; if(map[x][y] != '#' && !vis[x][y]) { vis[x][y] = 1; que.push( (struct node) {x,y,u.step+1}); } } } } int main() { int test; scanf(%d,&test); while(test--) { int sx,sy,ex,ey; scanf(%d %d,&m,&n); memset(map,'#',sizeof(map)); for(int i = 1; i <= n; i++) { scanf(%s,map[i]+1); for(int j = 1; j <= m; j++) { if(map[i][j] == 'S') { sx = i; sy = j; } if(map[i][j] == 'E') { ex = i; ey = j; } } } printf(%d %d %d ,dfs(sx,sy,ex,ey,0,1), dfs(ex,ey,sx,sy,0,1), bfs(sx,sy,ex,ey)); } return 0; }
