啊？这道题不是广搜吗？
by SwethessPotion @ 2024-07-18 20:51:08
@[kingsleykingsley](/user/1058091) AC Code:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 35;
bool vis[N][N];
int arr[N][N], n;
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};
queue<pair<int, int> > q;
void bfs(int i, int j)
{
vis[i][j] = true;
q.push({i, j});
while (!q.empty())
{
for (int i = 1; i <= 4; i++)
{
int xx = q.front().first + dx[i], yy = q.front().second + dy[i];
if (1 <= xx && xx <= n && 1 <= yy && yy <= n && arr[xx][yy] == 0 && !vis[xx][yy])
{
vis[xx][yy] = true;
q.push({xx, yy});
}
}
q.pop();
}
}
void input()
{
cin >> n;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> arr[i][j];
}
}
}
void startBfs()
{
for (int i = 1; i <= n; i++)
{
if (arr[i][1] == 0)
{
bfs(i, 1);
}
if (arr[1][i] == 0)
{
bfs(1, i);
}
if (arr[n][i] == 0)
{
bfs(n, i);
}
if (arr[i][n] == 0)
{
bfs(i, n);
}
}
}
void printAnswer()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (!vis[i][j] && arr[i][j] == 0)
{
cout << "2 ";
}
else
{
cout << arr[i][j] << " ";
}
}
cout << endl;
}
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
input();
startBfs();
printAnswer();
return 0;
}
```
by SwethessPotion @ 2024-07-18 20:52:25
谢谢谢
已关
by kingsleykingsley @ 2024-07-18 20:54:41
@[kingsleykingsley](/user/1058091) 深搜应该会t掉
by fire_flies @ 2024-07-18 20:55:09
@[kingsleykingsley](/user/1058091)
码风有点怪，见谅
```cpp
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x,y;
};
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
int n,a[31][31];
queue<node> q;
void bfs(int x,int y)
{
a[x][y]=0;
q.push(node{x,y});
while(!q.empty())
{
int xx=q.front().x,yy=q.front().y;
q.pop();
for (int i=0;i<4;i++)
{
int u=xx+dx[i],v=yy+dy[i];
if (u>=1 && u<=n && v>=1 && v<=n && a[u][v]==2)
{
if (a[u][v]==1)
break;
q.push(node{u,v});
a[u][v]=0;
}
}
}
return;
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
cin>>a[i][j];
if (a[i][j]==0)
a[i][j]=2;
}
}
for (int i=1;i<=n;i++)
{
if (a[i][1]==2)
bfs(i,1);
if (a[i][n]==2)
bfs(i,n);
if (a[1][i]==2)
bfs(1,i);
if (a[n][i]==2)
bfs(n,i);
}
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
cout<<a[i][j]<<' ';
cout<<endl;
}
return 0;
}
```
by KevinJoshua @ 2024-07-18 20:56:39
@[fire_flies](/user/1360902) t不掉的。剪枝啊，你看我
by Crab_Tang @ 2024-07-21 17:33:10
@[Crab_Tang](/user/1021365) 已懂，新学剪枝
by fire_flies @ 2024-07-21 18:11:26
@[kingsleykingsley](/user/1058091) 方案总和用dsf，最短路径用bsf
by wongyd @ 2024-07-23 16:55:38