Flood Fill算法BFS-城堡问题

城堡问题图1是一个城堡的地形图。请你编写一个程序计算城堡一共有多少房间最大的房间有多大。城堡被分割成 m∗n个方格区域每个方格区域可以有0~4面墙。注意墙体厚度忽略不计。输入格式第一行包含两个整数 m 和 n分别表示城堡南北方向的长度和东西方向的长度。接下来 m 行每行包含 n 个整数每个整数都表示平面图对应位置的方块的墙的特征。每个方块中墙的特征由数字 P 来描述我们用1表示西墙2表示北墙4表示东墙8表示南墙P 为该方块包含墙的数字之和。例如如果一个方块的 P 为3则 3 1 2该方块包含西墙和北墙。城堡的内墙被计算两次方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。输出格式共两行第一行输出房间总数第二行输出最大房间的面积方块数。数据范围1≤m,n≤50,0≤P≤15输入样例4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13输出样例5 9import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Main { static int N110; static int n,m; static int dx[]{-1,0,1,0}; static int dy[]{0,1,0,-1}; static int a[][]new int[N][N]; static boolean f[][]new boolean[N][N]; public static void main(String[] args) throws IOException { BufferedReader brnew BufferedReader(new InputStreamReader(System.in)); BufferedWriter bwnew BufferedWriter(new OutputStreamWriter(System.out)); StringTokenizer stnew StringTokenizer(br.readLine()); nInteger.parseInt(st.nextToken()); mInteger.parseInt(st.nextToken()); for (int i 1; i n; i) { stnew StringTokenizer(br.readLine()); for (int j 1; j m; j ){ a[i][j]Integer.parseInt(st.nextToken()); } } int res0,maxz0; for (int i 1; i n; i) { for (int j 1; j m; j) { if(!f[i][j]){ res; maxzMath.max(bfs(i,j), maxz); } } } bw.write(res\n); bw.write(maxz\n); br.close(); bw.flush(); bw.close(); } static int bfs(int x,int y){ int ans0; Queueint[] queuenew LinkedListint[](); queue.add(new int[]{x,y}); f[x][y]true; while(!queue.isEmpty()){ int no[]queue.poll(); int ino[0],jno[1]; ans; int posa[i][j]; if((pos1)!1 j-10 !f[i][j-1]){ queue.add(new int[]{i,j-1}); f[i][j-1]true; } if(((pos1)1)!1 i-10 !f[i-1][j]){ queue.add(new int[]{i-1,j}); f[i-1][j]true; } if(((pos2)1)!1 j1m !f[i][j1]){ queue.add(new int[]{i,j1}); f[i][j1]true; } if(((pos3)1)!1 i1n !f[i1][j]){ queue.add(new int[]{i1,j}); f[i1][j]true; } } return ans; } }