BFS-填涂颜色

深碍√TFBOYSˉ_ 2023-07-13 12:20 22阅读 0赞

# 题目描述 #

由数字000组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2;  
涂色前和涂色后的方阵如下：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]

## 输入输出样例 ##

**输入**

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

说明/提示  
1≤n≤30

## 感觉BFS的特点不太明显，拓展到最小连通图如何！！！ ##

import java.util.Scanner;
    public class 填涂颜色_BFS {
        
        static int n=0;
        static int[][]a=new int[32][32];
        public static void fn(int x,int y){
        
            if (x>=0&&x<=n+1&&y>=0&&y<=n+1){
        //在n*n的矩阵外再加了一层
                if (a[x][y]==1||a[x][y]==3){
        
                    return;
                }else {
        
                    a[x][y]=3;
                }
                fn(x-1,y);
                fn(x+1,y);
                fn(x,y-1);
                fn(x,y+1);
            }
        }
        public static void main(String[] args) {
        
            Scanner scanner=new Scanner(System.in);
            n=scanner.nextInt();
            int flag=0;
            for (int i = 1; i <=n ; i++) {
        
                for (int j = 1; j <=n ; j++) {
        
                    a[i][j]=scanner.nextInt();
                }
            }
            fn(0,0);
            for(int i=1;i<=n;i++) {
        
                for(int k=1;k<=n;k++) {
        
                    if(a[i][k]==3) a[i][k]=0;
                    else if(a[i][k]==0) a[i][k]=2;
                }
            }
            for(int i=1;i<=n;i++) {
        
                for(int k=1;k<=n;k++) {
        
                    System.out.print(a[i][k]+" ");
                }
                System.out.println();
            }
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: /images/20230529/1abf260a78f946ca9bd38af4c95049be.png