Midnight_szx @ 2023-01-09 21:11:57
一直挂第四个点，请大佬指正错误
我也不知道为什么非要写BFS折磨自己qwq
#include<iostream>
#include<queue>
using namespace std;
int n, map[35][35];
bool vis[35][35];
int to[5][2] = {{0, 0}, {1, 0}, {0, 1}, {-1, 0}, {0, -1}};
struct node {
int x, y;
};
queue<node> q;
inline void bfs(int a, int b) {
node t = {a, b};
q.push(t);
vis[a][b] = 1;
while(!q.empty()) {
node k = q.front();
int xx = k.x, yy = k.y;
q.pop();
for(int i = 1; i <= 4; i++) {
int kx = xx + to[i][0], ky = yy + to[i][1];
if(!vis[kx][ky] and kx > 0 and kx <= n and ky > 0 and ky <= n) {
vis[kx][ky] = 1;
node tmp = {kx, ky};
q.push(tmp);
}
}
}
}
int main() {
cin>>n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin>>map[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(map[i][j] == 1)
vis[i][j] = 1;
for(int i = 1; i <= n; i++)
if(map[i][1] == 0 and !vis[i][1])
bfs(i, 1);
for(int i = 1; i <= n; i++)
if(map[i][n] == 0 and !vis[i][n])
bfs(i, n);
for(int i = 1; i <= n; i++)
if(map[1][i] == 0 and !vis[1][i])
bfs(1, i);
for(int i = 1; i <= n; i++)
if(map[1][n] == 0 and !vis[1][n])
bfs(n, i);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
if(!vis[i][j] and map[i][j] == 0)
map[i][j] = 2;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++)
cout<<map[i][j]<<" ";
cout<<'\n';
}
return 0;
}by _Glassy_Sky_ @ 2023-01-09 21:27:55
你是超时了还是wa掉了？
by _Glassy_Sky_ @ 2023-01-09 21:28:11
@Midnight_szx
by Midnight_szx @ 2023-01-09 21:32:55
@FZwangmuem
wa
by _Glassy_Sky_ @ 2023-01-09 21:35:30
我的代码是这样的，我在写题，你对一下
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 10;
int a[maxn][maxn];
int dx[5] = {0, 0, 1, -1};
int dy[5] = {1, -1, 0, 0};
int n;
void dfs(int x, int y)
{
if(a[x][y] == 0)
{
a[x][y] = 3;
for(int i = 0; i < 4; i ++)
{
int nx = x + dx[i], ny = y + dy[i];
if(nx > 0 && nx <= n && ny > 0 && ny <= n)
dfs(nx, ny);
}
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
cin >> a[i][j];
for(int i = 1; i <= n; i ++)
{
dfs(i, 1);
dfs(i, n);
dfs(1, i);
dfs(n, i);
}
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
if(a[i][j] == 3) cout << "0 ";
if(a[i][j] == 0) cout << "2 ";
if(a[i][j] == 1) cout << "1 ";
}
cout << endl;
}
return 0;
}by _Glassy_Sky_ @ 2023-01-09 21:35:51
也是BFS
by Midnight_szx @ 2023-01-09 21:36:42
@FZwangmuem 《BFS》emm...
by MinCat @ 2023-01-09 21:36:46
您是wa了#4对吧
输入：
20
0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0
1 1 1 1 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 1 1 1 1 0 0 0 1 1 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 1 1 1 1
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0
正确的输出：
0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
1 1 1 1 1 2 1 1 1 1 1 1 2 1 0 0 0 0 0 0
1 2 2 2 2 2 2 2 2 2 2 2 2 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 2 1
0 0 0 0 0 0 0 0 1 2 1 1 1 1 2 2 2 1 1 1
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 1 1 0 0
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 1 1 1 1
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 2 2 2 2 1
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 1 1 1 1
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 2 1 0 0 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0
您的输出：
0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
0 0 0 0 1 2 1 0 0 0 0 1 2 1 0 0 0 0 0 0
1 1 1 1 1 2 1 1 1 1 1 1 2 1 0 0 0 0 0 0
1 2 2 2 2 2 2 2 2 2 2 2 2 1 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 1 2 2 2 2 2 2 2 2 2 2 1
0 0 0 0 0 0 0 0 1 2 1 1 1 1 2 2 2 1 1 1
0 0 0 0 0 0 0 0 1 2 1 2 2 1 2 1 1 1 0 0
0 0 0 0 0 0 0 0 1 2 1 2 2 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 2 1 2 2 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 2 1 2 2 1 2 1 1 1 1 1
0 0 0 0 0 0 0 0 1 2 1 2 2 1 2 2 2 2 2 1
0 0 0 0 0 0 0 0 1 2 1 2 2 1 2 1 1 1 1 1
0 0 0 0 0 0 0 0 1 2 1 2 2 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 2 1 2 2 1 2 1 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 2 2 1 1 1 0 0 0 0
by MinCat @ 2023-01-09 21:37:20
这个很容易看出来吧
by _Glassy_Sky_ @ 2023-01-09 21:37:53
@Midnight_szx 写错了。。。
by Midnight_szx @ 2023-01-09 21:38:10
@OIer_zhez 看当然是看得出来