洛谷題解-P1162填塗顔色

題目概況

題目連結： https://www.luogu.com.cn/problem/P1162

難度： 普及-

題目分析

簡化題目： 把圖中

1

包裹起來的部分全部寫成

2

。

涉及知識點： 深度優先搜尋DFS

解題思路：

我們可以反其道而行之。采用染色法，将

1

圍欄外的元素全部标記，然後剩下沒有被染色的部分即為圍欄以内的。

在輸入時要把圍牆提前染色标記。在

0,0

~

n+1,n+1

搜尋（因為還可能有邊邊上的沒被圍住的，這點比較特殊，比如下面的一組資料），再染色。

6
0 0 1 1 1 0
1 1 1 0 1 0
1 0 0 0 0 1
1 1 0 1 1 1
0 1 0 1 0 0
0 1 1 1 0 0

           

代碼拆解及要點分析

老規矩，普及-的題目不寫拆解分析

完整代碼

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 35;
int n;
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}}; //四個方向
int ma[MAXN][MAXN], vis[MAXN][MAXN]; //ma是圖，vis是标記數組

bool in(int a, int b) { //範圍内判斷函數
	return a >= 0 && a <= n + 1 && b >= 0 && b <= n + 1;
}

void dfs(int x, int y) {
	for (int i = 0; i < 4; i++) {
		int tx = x + dir[i][0];
		int ty = y + dir[i][1];
		if (in(tx, ty) && vis[tx][ty] == 0) { //在範圍内，這不是個圍牆
			vis[tx][ty] = 1; //染個色
			dfs(tx, ty); //繼續
		}
	}
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> ma[i][j];
			if (ma[i][j] == 1 ){
				vis[i][j] = 1; //圍牆提前染色标記
			}
		}
	} 
	dfs(0,0);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (vis[i][j] == 0) { //如果經過dfs沒有被染色，那麼就在圍牆内
				cout << 2 << " ";
			} else {
				cout << ma[i][j] << " "; //原模樣輸出
			}
		}
		cout << endl;
	}
	return 0;
}