1 #include<iostream>  2 #include<cstdio>  3 #include<cstdlib>  4 #include<cstring>  5 #include<string>  6 #include<queue>  7 #include<algorithm>  8 #include<map>  9 #include<iomanip> 10 #include<climits> 11 #include<string.h> 12 #include<stdlib.h> 13 #define INF 1e11 14 #define MAXN 60 15 using namespace std; 16  17 struct node { 18     int x1, y1; 19     int x2, y2; 20     bool ok; 21 }a[30]; 22  23 struct dir{ 24     int x, y; 25     int step; 26 }; 27  28 int dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, 1, -1 }; 29 int T, n, m; 30 char mp[MAXN][MAXN]; 31 int vis[MAXN][MAXN]; 32 int sx, sy, fx, fy; 33 int num; 34 map<node, node> s; 35  36 bool judge(int x, int y) 37 { 38     if ( vis[x][y] || x < 0 || y < 0 || x >= n || y >= m) 39         return true; 40     return false; 41 } 42  43 int bfs() 44 { 45     queue<dir> q; 46     q.push({sx,sy,false}); 47     vis[sx][sy] = true; 48     while (!q.empty()) 49     { 50         dir now = q.front(); 51         q.pop(); 52         if (now.x == fx && now.y == fy) { 53             return now.step; 54         } 55         //cout << "x = " << now.x; 56         //cout << "  y = " << now.y << endl; 57         dir next; 58         next.step = now.step + 1; 59         for (int i = 0; i < 4; ++i) { 60             next.x = now.x + dx[i]; 61             next.y = now.y + dy[i]; 62             if (judge(next.x,next.y)) continue; 63             if (mp[next.x][next.y] == ‘#‘)  continue; 64             if (mp[next.x][next.y] == ‘.‘ || mp[next.x][next.y] == ‘Q‘) { 65                 q.push({ next.x, next.y,next.step}); 66                 vis[next.x][next.y] = true; 67  68             } 69             if (mp[next.x][next.y] >= ‘a‘ && mp[next.x][next.y] <= ‘z‘) { 70                 //cout << "ok" << endl; 71                 int k = mp[next.x][next.y] - ‘a‘; 72                 if (next.x == a[k].x1 && next.y == a[k].y1) { 73                     q.push({ a[k].x2, a[k].y2, next.step }); 74                     //vis[a[k].x1][a[k].y1] = true;     错误的标记 75                     vis[next.x][next.y] = true; 76                 } 77                 else { 78                     q.push({ a[k].x1, a[k].y1, next.step}); 79                     //vis[next.x][next.y] = true;        错误的标记 80                     vis[a[k].x2][a[k].y2] = true; 81                 } 82             } 83         } 84     } 85     return -1; 86 } 87  88 void init() 89 { 90     memset(a, 0, sizeof(a)); 91     memset(vis, 0, sizeof(vis)); 92     num = 0; 93 } 94  95 void process() 96 { 97     init(); 98     cin >> n >> m; 99     for (int i = 0; i < n; ++i)100         cin >> mp[i];101     for (int i = 0; i < n; ++i)102         for (int j = 0; j < m; ++j) {103             if (mp[i][j] == ‘Q‘)104                 fx = i, fy = j;105             else if (mp[i][j] == ‘L‘)106                 sx = i, sy = j;107             else if (mp[i][j] >= ‘a‘ && mp[i][j] <= ‘z‘){108                 int k = mp[i][j] - ‘a‘;109                 if (a[k].ok == false) {110                     a[k].x1 = i;111                     a[k].y1 = j;112                     a[k].ok = true;113                 }114                 else {115                     a[k].x2 = i;116                     a[k].y2 = j;117                 }118             }119         }120     //cout << "sx = " << sx << " sy =" << sy << endl;121     //cout << "fx = " << fx << " fy =" << fy << endl;122     cout << bfs() << endl;123 }124 125 int main()126 {127     cin >> T;128     while (T--)129         process();130     //system("pause");131     return 0;132 }