炫意html5
最早CSS3和HTML5移动技术网站之一

填涂颜色(dfs)

#include<iostream>
using namespace std;
const int MAXN = 30 + 5;
int n;
int map[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[] = { 0, 0, 0, -1, 1};
int dy[] = { 0, 1, -1, 0, 0};
void dfs(int x, int y)
{
if(x >= 0 && x <= n + 1 && y >= 0 && y <= n + 1)
{
if(map[x][y] == 1 || map[x][y] == 3)
return;
else
{
map[x][y] = 3;
for(int i = 1; i <= 4; i++)
dfs(x + dx[i], y + dy[i]);
}
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> map[i][j];
dfs(0, 0);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(map[i][j] == 3)
map[i][j] = 0;
else if(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 << endl;
}
return 0;
}

以上是代码 1 , 为AC代码

#include<iostream>
using namespace std;
const int MAXN = 30 + 5;
int n;
int map[MAXN][MAXN];
bool vis[MAXN][MAXN];
int dx[] = { 0, 0, 0, -1, 1};
int dy[] = { 0, 1, -1, 0, 0};
void dfs(int x, int y)
{
if(x >= 1 && x <= n && y >= 1 && y <= n)
{
if(map[x][y] == 1 || map[x][y] == 3)
return;
else
{
map[x][y] = 3;
for(int i = 1; i <= 4; i++)
dfs(x + dx[i], y + dy[i]);
}
}
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> map[i][j];
dfs(1, 1);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(map[i][j] == 3)
map[i][j] = 0;
else if(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 << endl;
}
return 0;
}

以上为代码 2,为错误代码,只得了32 分,只有 dfs( )中 if( )里面和 dfs( )调用的参数有差别,样例都过了,但是搞不懂为什么,求解!谢谢!

回答

问题补充:

我的解题思路就是,先把 1 围成的圈外的 0 用 dfs 搜索连通块,然后赋值为 3 ,接着遍历整个图形,为 3 的赋为 0, 为 0 的赋为 2,

炫意HTML5 » 填涂颜色(dfs)

Java基础教程Android基础教程