题目传送门
解题思路:
bfs走迷宫.
AC代码:
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 6 using namespace std; 7 8 int n,x,y,bx,by,ans = 199999999; 9 int wayx[4] = {-1,0,1,0}; 10 int wayy[4] = {0,-1,0,1}; 11 char a[101][101]; 12 bool vis[101][101][4]; 13 struct kkk { 14 int step,xx,yy; 15 int direction; 16 }e; 17 queue<kkk> q; 18 19 inline void bfs() { 20 for(int i = 0;i <= 3; i++) { 21 kkk k; 22 k.step = 0; 23 k.direction = i; 24 k.xx = x; 25 k.yy = y; 26 q.push(k); 27 vis[x][y][i] = 1; 28 } 29 while(!q.empty()) { 30 kkk p = q.front(); 31 q.pop(); 32 if(p.xx == bx && p.yy == by) ans = min(ans,p.step); 33 for(int i = 0;i <= 3; i++) { 34 kkk o; 35 if((i + p.direction) % 2 == 1) { 36 o.direction = i; 37 o.step = p.step + 1; 38 o.xx = p.xx; 39 o.yy = p.yy; 40 } 41 if(i == p.direction) { 42 o.direction = i; 43 o.step = p.step; 44 o.xx = p.xx + wayx[i]; 45 o.yy = p.yy + wayy[i]; 46 } 47 if(!vis[o.xx][o.yy][o.direction] && a[o.xx][o.yy] != 'x' && o.xx >= 1 && o.xx <= n && o.yy >= 1 && o.yy <= n) { 48 q.push(o); 49 vis[o.xx][o.yy][o.direction] = 1; 50 } 51 } 52 } 53 } 54 55 int main() { 56 scanf("%d",&n); 57 for(int i = 1;i <= n; i++) 58 for(int j = 1;j <= n; j++) { 59 cin >> a[i][j]; 60 if(a[i][j] == 'A') x = i,y = j; 61 if(a[i][j] == 'B') bx = i,by = j; 62 } 63 bfs(); 64 if(ans == 199999999) printf("-1"); 65 else 66 printf("%d",ans); 67 return 0; 68 }