思路：
bfs，用状压表示走过的区域，然后和x1，y1，x2，y2构成所有的状态，然后标记一下就可以了
代码：
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head bool vis[(1<<16) + 10][5][5][5][5]; int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0}; char s[10][10]; int n, m; struct node { int x1, y1, x2, y2, dis, st; }; int get(int x, int y) { return (x-1)*m + y - 1; } int bfs() { queue<node> q; int st = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if(s[i][j] == 'S' || s[i][j] == 'X') st |= 1<<get(i, j); } } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if(s[i][j] == 'S') { q.push(node{i, j, i, j, 0, st}); break; } } } while(!q.empty()) { node now = q.front(); q.pop(); if(now.st == (1<<n*m) - 1) return now.dis; if(!vis[now.st][now.x1][now.y1][now.x2][now.y2]) vis[now.st][now.x1][now.y1][now.x2][now.y2] = true; else continue; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { int x = now.x1 + dir[i][0]; int y = now.y1 + dir[i][1]; int xx = now.x2 + dir[j][0]; int yy = now.y2 + dir[j][1]; if(1 <= x && x <= n && 1 <= y && y <= m && 1 <= xx && xx <= n && 1 <= yy && yy <= m && s[x][y] != 'X' && s[xx][yy] != 'X') { q.push(node{x, y, xx, yy, now.dis+1, now.st|(1<<get(x, y))|(1<<get(xx, yy))}); } } } } return 0; } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%s", s[i]+1); } printf("%d ", bfs()); return 0; }