P1162 填涂颜色题解

【问题分析】

• 分析题目可得此问题为连通块问题
• 因此题枚举被包围的‘0’较难
• 所以可用枚举每一个不被包围的‘0’

【设计程序】

#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 30 + 5;
int n, d[N][N];
bool vis[N][N]; 
int dt[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
//四种扩展方法

void dfs (int x, int y)//描述点的位置
{
	vis[x][y] = 1;//标记为未包围
	for (int i = 0;i < 4; i++)
	{
		int vx, vy;
		vx = x + dt[i][0];
		vy = y + dt[i][1];
		if (vx < 1 || vx > n || vy < 1 || vy > n)	continue;
        	//不符合的跳过
		if (vis[vx][vy] || d[vx][vy])	continue;
		//不符合的跳过
		dfs (vx, vy) ; 
	}
}
int main()
{
	int i, j;
	scanf ("%d", &n);
	for (int i = 1;i <= n; i++)
		for (int j = 1;j <= n; j++)
			scanf ("%d", &d[i][j]);
	for (int i = 1;i <= n; i++)
	//找到四个角上不被包围的‘0’并标记
	{
		if (!vis[1][i] && !d[1][i])	dfs(1, i);
		if (!vis[n][i] && !d[n][i])	dfs(n, i);
		if (!vis[i][1] && !d[i][1])	dfs(i, 1);
		if (!vis[i][n] && !d[i][n])	dfs(i, n);
	}

	for (int i = 1;i <= n; i++)	
	{
		for (int j = 1;j <= n; j++)
		{
			if (!vis[i][j] && !d[i][j])	printf ("2 ");
			//如果没被标记且原为‘0’用2代替
			else 	printf ("%d ", d[i][j]);
		}
		printf ("\n");
	}
	return 0;
}

【调试代码】
1.测试样例，
2.自测数据（边界值或特殊值）（搜索一般测试样例就行了）

完结撒花！！