一.题目描述:
二.解题思路:
输入的时候先把各种装置存起来,再记录一下起点坐标,进行bfs,一到装置处就循环找到另一处装置,然后直到到达出口,每次到出口都更新一下到达的最小距离即可。
三.代码实现:
1 #include "bits/stdc++.h" 2 using namespace std; 3 char mp[310][310]; 4 char bk[310][310]; 5 int mv[4][2] = {{0,1},{0,-1},{-1,0},{1,0}}; 6 int wmv[100000][2]; 7 int minstep = INT_MAX; 8 struct node{ 9 int x; 10 int y; 11 int step; 12 }; 13 int k; 14 int n,m; 15 void bfs(int sx,int sy) 16 { 17 queue <node> ans; 18 node u; 19 u.x = sx; 20 u.y = sy; 21 u.step = 0; 22 int head = 1,tail = 1; 23 ans.push(u); 24 tail++; 25 while(head < tail){ 26 node v = ans.front(); 27 if(mp[v.x][v.y] == '=') {minstep = min(minstep,v.step);return;} 28 ans.pop(); 29 for(int i = 0;i < 4;i++){ 30 int dx = v.x + mv[i][0]; 31 int dy = v.y + mv[i][1]; 32 node w; 33 if(dx < 0 || dy < 0 || dx >= n || dy >= m) continue; 34 if(mp[dx][dy] == '#' || bk[dx][dy]) continue; 35 bk[dx][dy] = 1; 36 if(mp[dx][dy] >= 'A' && mp[dx][dy] <= 'Z'){ 37 for(int i = 0;i < k;i++) 38 if((dx != wmv[i][0] || dy != wmv[i][1]) && mp[dx][dy] == mp[wmv[i][0]][wmv[i][1]]){ 39 dx = wmv[i][0]; 40 dy = wmv[i][1]; 41 break; 42 } 43 } 44 w.x = dx; 45 w.y = dy; 46 w.step = v.step + 1; 47 tail++; 48 ans.push(w); 49 } 50 head++; 51 } 52 } 53 int main() 54 { 55 int sx,sy; 56 cin >> n >> m; 57 getchar(); 58 for(int i = 0;i < n;i++){ 59 for(int j = 0;j < m;j++){ 60 cin >> mp[i][j]; 61 if(mp[i][j] == '@') 62 sx = i,sy = j; 63 else if(mp[i][j] >= 'A' && mp[i][j] <= 'Z') 64 wmv[k][0] = i,wmv[k++][1] = j; 65 } 66 getchar(); 67 } 68 bfs(sx,sy); 69 cout << minstep << endl; 70 return 0; 71 }