洛谷P1162 填涂颜色 题解

题目描述

由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如：6 \times 66×6的方阵（n=6n=6），涂色前和涂色后的方阵如下：

0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1

输入输出格式

输入格式：

每组测试数据第一行一个整数n(1 \le n \le 30)n(1≤n≤30)

接下来nn行，由00和11组成的n \times nn×n的方阵。

方阵内只有一个闭合圈，圈内至少有一个00。

输出格式：

已经填好数字22的完整方阵。

输入输出样例

输入样例#1：

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

输出样例#1：

0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1

说明

1 \le n \le 301≤n≤30

---

题解：

这是一道简单的搜索题，把圈外的元素都搜一遍并赋值-1，从一点向四个方向搜索，越界或不等于0时停止；

第一次提交时坑了我一下，题意是闭合圈而不是闭合圆，所以不能只设四个角为搜索起点，要把四条边上的所有元素都设置成搜索起点，遇到圈就会return；

现在圈外元素全部为-1，圈内元素为0；圈为1，三级划分已经很明显了，直接按照题意输出就OK；

#include <iostream> using namespace std; int n,a[31][31]; void dfs(int x, int y) { if (x<1||y<1||x>n||y>n||a[x][y] != 0)return; a[x][y] = -1; dfs(x + 1, y); dfs(x - 1, y); dfs(x, y + 1); dfs(x, y - 1); } 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++) { if (a[i][1] != 1) dfs(i, 1); if (a[i][n] != 1) dfs(i, n); } for (int i = 1; i <= n; i++) { if (a[1][i] != 1) dfs(1, i); if (a[n][i] != 1) dfs(n, i); } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (a[i][j] == -1) { cout << '0' << ' '; } else if (a[i][j] == 1) { cout << '1' << ' '; } else { cout << '2' << ' '; } } cout << endl; } return 0; }

---