位置互换
内存限制: 256 Mb时间限制: 1000 ms
题目描述
迷宫游戏是在一张 n×m的网格图中进行的，其中 a(i,j) 表示第 i 行、第 j 列网格的状态，每个网格有以下 4 种情况：
- 若a(i,j)为
.，则表示该位置为可以走的空地 - 若a(i,j)为
#，则表示该位置为不可走的墙壁 - 若a(i,j)为
1，则表示该位置为小爱初始的位置 - 若a(i,j)为
2，则表示该位置为小艾初始的位置
每一轮游戏开始时，可以自由决定是小爱先移动还是小艾先移动，他们可以移动至相邻的上下左右四个空格或原地不动，但又不可以移动至对方所在的网格中。
请问，游戏最少进行多少轮，才能使小爱和小艾互换位置？
输入格式
输入第一行，两个正整数分别表示 n,m
接下来的第 2 行至第 n+1 行，每行 m 个字符，其中第 i+1 行、第 j 列的字符表示初始时网格 a(i,j) 的状态。
输出格式
输出共一行，一个整数表示两人互换位置最少需要的轮数，若无法完成，则输出 No Solution。
数据范围
- 对于 50%的数据，1≤n,m≤5
- 对于 100%的数据，1≤n,m≤30
样例数据
输入:
3 3
1..
...
..2
输出:
4
说明:
1.. .1. ..1 ... 2..
... --> ... --> ... --> 2.1 --> ...
..2 .2. 2.. ... ..1
输入:
3 3
1..
###
..2
输出:
No Solution
说明:
被第二行的墙挡住了
输入:
2 3
1.2
#.#
输出:
4
说明:
1.2 .12 .2. 21. 2.1
#.# --> #.# --> #1# --> #.# --> #.#
输入:
3 3
1.#
#.#
#.2
输出:
No Solution
解析：感谢杰哥提供的解题思路及代码（gzh 跟杰哥玩编程）
BFS
加了限制的宽搜，样例把一些极端情况都给出了，所以要想办法突破限制。
以下问题要解决：
从样例3可知，走过的还能走，如何解决？
从样例3可知，可以一个走，一个不走，如何解决？
从样例4可知，独木桥无法通过，如何解决？
如何解决一个人提前到了，另一个人还要走的问题？
如果分别用一个二维数组记录两人走过的位置，基本走远了，很难解决走过还能再走的问题。
问题1:两个人走过的位置需要两个坐标，如果用维数组记录走过的位置，则哪怕走过了，只要坐标的组合没出现过，还能往回走。
问题2:这个问题发生在两人都走向同一个格子的时候，那么特判处理一下，让一个走，一个不走，记录状态即可，需要注意一个走，一个不走有两种情况，都要处理。
问题3:独木桥走法唯一，只要判断两个坐标是否发生了交换这种情况，如果发生交换，则不处理，那么没有数据入队，程序提前结束，输出无法完成的信息即可。
问题4:计算出新位置的时候，特判一下是否已经到达目标位置，如果到达了，则修改为目标坐标，这样实现了一个人到了终点，另一个还能继续前进。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 40;
struct node{
pair<int,int> a,b;
int step;
};
int n,m;
char mp[maxn][maxn];
bool vis[maxn][maxn][maxn][maxn];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
pair<int,int> a_start,b_start;
bool check(int x, int y)
{
return x > 0 && x <= n && y > 0 && y <= m && mp[x][y]!='#';
}
int bfs(pair<int,int> a_start, pair<int,int> b_start)
{
queue<node> q;
q.push({a_start,b_start,0});
vis[a_start.first][a_start.second][b_start.first][b_start.second]=1;
while(q.size()){
pair<int,int> a = q.front().a;
pair<int,int> b = q.front().b;
int steps = q.front().step;
q.pop();
if(a == b_start && b == a_start){ //目标状态
return steps;
}
for(int i = 0; i < 4; i++){ //枚举所有的方向组合
for(int j = 0; j < 4; j++){
int na_x = a.first + dx[i],na_y = a.second + dy[i];
int nb_x = b.first + dx[j],nb_y = b.second + dy[j];
if (a == b_start) na_x = b_start.first,na_y = b_start.second; //已到终点，保持不动
if (b == a_start) nb_x = a_start.first,nb_y = a_start.second; //已到终点，保持不动
if(na_x==b.first && na_y == b.second && nb_x==a.first && nb_y==a.second) continue; //发生交换，规则不允许
if (check(na_x, na_y) && check(nb_x,nb_y)){
if(na_x == nb_x && na_y == nb_y){ //两人移到同一个格子的情况
if(!vis[na_x][na_y][b.first][b.second]){ //a不动
vis[na_x][na_y][b.first][b.second] = 1;
q.push({{na_x, na_y}, {b.first, b.second}, steps + 1});
}
if(!vis[a.first][a.second][nb_x][nb_y]){ //b不动
vis[a.first][a.second][nb_x][nb_y] = 1;
q.push({{a.first, a.second}, {nb_x, nb_y}, steps + 1});
}
continue;
}
if (!vis[na_x][na_y][nb_x][nb_y]) { //普通情况
vis[na_x][na_y][nb_x][nb_y] = 1;
q.push({{na_x, na_y}, {nb_x, nb_y}, steps + 1});
}
}
}
}
}
return -1;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
cin>>mp[i][j];
if(mp[i][j]=='1') a_start={i,j};
if(mp[i][j]=='2') b_start={i,j};
}
int res = bfs(a_start,b_start);
if(res == -1) cout<<"No Solution"<<"\n";
else cout<<res<<"\n";
return 0;
}
