染色法,与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); } }