填涂颜色

题目描述

由数字 0 0 0组成的方阵中，有一任意形状闭合圈，闭合圈由数字 1 1 1构成，围圈时只走上下左右 4 4 4个方向。现要求把闭合圈内的所有空间都填写成 2 2 2.例如： 6 × 6 6 imes 6 6×6的方阵（ n = 6 n=6 n=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 ≤ n ≤ 30 ) n(1 le n le 30) n(1≤n≤30)

接下来 n n n行，由 0 0 0和 1 1 1组成的 n × n n imes n n×n的方阵。

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

输出格式

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

样例 #1

样例输入 #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

思路

dfs把1外围的所有0标记,因为1是只能上下左右的连接，所以不存在对角线 把没有标记的0填为2就好了

代码

import java.util.*;

public class Main {
          
   
    static int[][] upDownLeftRight = {
          
   {
          
   -1,0},{
          
   1,0},{
          
   0,-1},{
          
   0,1}};
    static int row;
    static int col;
    public static void dfs(boolean[][] flag, int[][] arr, int x, int y) {
          
   
        for (int i = 0; i < 4; i++) {
          
   
            int newX = x + upDownLeftRight[i][0];
            int newY =  y + upDownLeftRight[i][1];
            if (newX < 0 || newX >= row || newY < 0 || newY >= col || arr[newX][newY] == 1) {
          
   
                continue;
            }
            if (!flag[newX][newY]) {
          
   
                flag[newX][newY] = true;
                dfs(flag, arr, newX, newY);
            }

        }
    }
    public static void main(String[] args) {
          
   
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        row = n;
        col = n;
        int[][] arr = new int[n][n];
        boolean[][] flag = new boolean[n][n];

        for (int i = 0; i < n; i++) {
          
   
            for (int j = 0; j < n; j++) {
          
   
                arr[i][j] = sc.nextInt();
            }
        }
        // 第一行
        for (int i = 0; i < n; i++) {
          
   
            if (arr[0][i] == 0 && !flag[0][i]) {
          
   
                dfs(flag, arr, 0, i);
            }
        }
        // 最后一行
        for (int i = 0; i < n; i++) {
          
   
            if (arr[n-1][i] == 0 && !flag[n-1][i]) {
          
   
                dfs(flag, arr, n-1, i);
            }
        }
        // 第一列
        for (int i = 0; i < n; i++) {
          
   
            if (arr[i][0] == 0 && !flag[i][0]) {
          
   
                dfs(flag, arr, i, 0);
            }
        }
        // 最后一列
        for (int i = 0; i < n; i++) {
          
   
            if (arr[i][n-1] == 0 && !flag[i][n-1]) {
          
   
                dfs(flag, arr, i, n-1);
            }
        }
        for (int i = 0; i < n; i++) {
          
   
            for (int j = 0; j < n; j++) {
          
   
                if (arr[i][j] == 0 && !flag[i][j]) {
          
   
                    arr[i][j] = 2;
                }
            }
        }
        for (int i = 0; i < n; i++) {
          
   
            for (int j = 0; j < n; j++) {
          
   
                if (j != n-1) {
          
   
                    System.out.print(arr[i][j]+" ");
                } else {
          
   
                    System.out.println(arr[i][j]);
                }
            }
        }
    }
}