题解(DFS做法)
2024-09-30 21:48:50
发布于:上海
9阅读
0回复
0点赞
我的思路:
先把所有的除了1以外的和边框上的0全部涂成2
接着洪水填充,从周围一圈开始,把所有能填充到的变成0
不算难题,基本会DFS就能做
点个赞吧球球了
//先把所有的除了1以外的和边框上的0全部涂成2
//接着洪水填充,从周围一圈开始,把所有能填充到的变成0
#include <iostream>
using namespace std;
int n;
int a[35][35];
bool vis[35][35];
// DFS 访问边界的 0
void dfs(int curx, int cury)
{
if (curx < 1 || curx > n || cury < 1 || cury > n || vis[curx][cury] || a[curx][cury] != 0)
{
return;
}
vis[curx][cury] = true;
a[curx][cury] = -1; // 标记为已访问
dfs(curx + 1, cury);
dfs(curx - 1, cury);
dfs(curx, cury + 1);
dfs(curx, cury - 1);
}
int main()
{
cin >> n;
// 读入矩阵
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cin >> a[i][j];
}
}
// 从边界的0开始DFS
for (int i = 1; i <= n; i++)
{
if (a[i][1] == 0) dfs(i, 1);
if (a[i][n] == 0) dfs(i, n);
}
for (int j = 1; j <= n; j++)
{
if (a[1][j] == 0) dfs(1, j);
if (a[n][j] == 0) dfs(n, j);
}
// 填充闭合圈内的0为2
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (a[i][j] == 0)
{
a[i][j] = 2; // 填充为2
}
// 将标记为-1的0恢复为0
if (a[i][j] == -1)
{
a[i][j] = 0;
}
}
}
// 输出结果
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
return 0;
}
这里空空如也
有帮助,赞一个