2025牛客WC1-C-兢兢业业之移 · znzryb
## 思路讲解
[https://blog.csdn.net/lymww/article/details/122566800](https://blog.csdn.net/lymww/article/details/122566800)
bfs路径还原可以用bfs生成树（也就是树）的性质，即每个节点只有唯一的父节点这一性质进行还原，具体就是在bfs搜索过程中记录节点的父节点
那么这道题就是bfs找到最近的1，然后路径还原就行
## AC代码
AC
[https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75103248](https://ac.nowcoder.com/acm/contest/view-submission?submissionId=75103248)
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef array<int,4> arr;
const ll MAXN=110;
ll N,T;
bool vis[MAXN][MAXN]; // 总体vis
char maze[MAXN][MAXN];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void solve(){
vector<arr> out;
cin>>N;
memset(vis,false,sizeof(vis));
for(int i=1;i<=N;++i) {
for(int j=1;j<=N;++j) {
cin>>maze[i][j];
}
}
for(int i=1;i<=N/2;++i) {
for(int j=1;j<=N/2;++j) {
if(maze[i][j]=='1') {vis[i][j]=true;continue;}
queue<pii> q;
q.push({i,j});
vector<vector<pii> > pa(N+1,vector<pii>(N+1,{0,0}));
pa[i][j]={i,j};
// bfs
while (!q.empty()) {
int x=q.front().first,y=q.front().second;
q.pop();
for(int k=0;k<=3;++k) {
int u=x+dx[k],v=y+dy[k];
if(u<1||u>N) continue;
if(v<1||v>N) continue;
if(vis[u][v]) continue; // 不能动已经确定的点
if(pa[u][v].first!=0) continue; // 确定了父节点的点，说明是跑过的点，跳过
pa[u][v]={x,y};
q.push({u,v});
if(maze[u][v]=='1') { // 找到了，回溯路径
int o=u,p=v;
// 找根节点
while (pa[o][p].first!=o || pa[o][p].second!=p) {
swap(maze[o][p],maze[pa[o][p].first][pa[o][p].second]);
out.push_back({o,p,pa[o][p].first,pa[o][p].second});
tie(o,p)=pa[o][p];
// o=pa[o][p].first;
// p=pa[o][p].second;
}
// cout<<"pa:"<<i<<' '<<j<<'\n';
// for(int i1=1;i1<=N;++i1) {
// for(int j1=1;j1<=N;++j1) {
// cout<<pa[i1][j1].first<<'_'<<pa[i1][j1].second<<' ';
// }
// cout<<'\n';
// }
// swap(maze[i][j],maze[u][v]);
goto outer; // 跳出整个bfs
}
}
}
outer:
vis[i][j]=true;
}
}
cout<<out.size()<<'\n';
for(int i=0;i<out.size();++i) {
cout<<out[i][0]<<' '<<out[i][1]<<' '<<out[i][2]<<' '<<out[i][3]<<'\n';
}
// cout<<"debug\n";
// for(int i=1;i<=N;++i) {
// for(int j=1;j<=N;++j) {
// cout<<maze[i][j];
// }
// cout<<'\n';
// }
// for(int i=1;i<=N;++i) {
// for(int j=1;j<=N;++j) {
// cout<<vis[i][j];
// }
// cout<<'\n';
// }
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while (T--) {
solve();
}
return 0;
}
/*
1
4
1111
0000
0000
0000
1
4
0001
0010
0100
1000
1
4
1010
0100
0100
0000
*/
```
## 心路历程（WA，TLE，MLE……）
这个蓝注释的地方就是原来有错的地方，这种只有同时更新（用tie，或者其他才行）
否则先更新了o，后面p的结果就不对了
还有什么out忘记清空什么的，这就不多说了