洛谷P1506染色法Java解题

• 题目大意
• 具体代码

染色法，与bfs有一点相似，但是不是找到到达特定位置的路径而是一直走到头，所以直接迭代即可，没有回溯。

创建二维数组表示点的位置，然后一维数组表示四个方向的查找，开始的查找位置从矩形的四条边开始（如果是找最短路径应该是从指定的位置往前查找）。

import java.util.Scanner;
public class BFS染色法 {
    static int n,m,s = 0;
    static int[] kx = {0,1,0,-1};
    static int[] ky = {1,0,-1,0};
    static int[][] a = new int[501][501];

    public static void search(int x,int y){
        a[x][y] = 1;
        for(int i = 0;i < 4;i++){
            int x0 = x+kx[i];
            int y0 = y+ky[i];
            if((x0>0 && x0<=n)&&(y0>0 && y0<=m)&&(a[x0][y0] == 0)){
                search(x0,y0);
                //此处不可以标记，因为回溯可能会经过
            }
        }
    }//本题只是判断能走到的所有位置，所以只是迭代找路即可，不用回溯
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        for(int i = 1;i <= n;i++){
            String ls = sc.next();
            //此处不可以用nextline，会将/n一起读进去，导致/n作为一行而超出长度
            for(int j = 1;j <= m;j++){
                char l = ls.charAt(j-1);
                if(l == '*')a[i][j] = 1;
            }
        }

        //从四边找突破路线，两行边和两列边
        for(int i = 1;i <= n;i++){
            if(a[i][1] == 0)search(i,1);
            if(a[i][m] == 0)search(i,m);
        }

        for(int j = 1;j <= m;j++){
            if(a[1][j] == 0)search(1,j);
            if(a[n][j] == 0)search(n,j);
        }

        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                if(a[i][j] == 0)s++;
            }
        }

        System.out.println(s);
    }
}