AcWing 1098. 城堡问题
原题链接
简单
作者:
栗子ing
,
2022-05-14 16:09:19
,
所有人可见
,
阅读 231
import java.util.*;
public class Main{
static int N = 60,n,m,hh,tt;
static int[][] g = new int[N][N];//地图
static boolean[][] st = new boolean[N][N];//标记来没来过
static int[] dx = {0,-1,0,1};//能够走的方向
static int[] dy = {-1,0,1,0};//顺序定义按照他的顺序,西北东南
static PII[] q = new PII[N * N];
public static int bfs(int x,int y){
hh = 0 ; tt = -1;
q[++ tt] = new PII(x,y);
st[x][y] = true;
int res = 0;
while (hh <= tt){
PII t = q[hh ++ ];//堆存入多少,房间就有多大
res ++;//弹出一个就++,全部弹出就结束
for (int i = 0 ; i < 4 ; i ++ ){
int a = t.x + dx[i],b = t.y + dy[i];
if(a < 0 || a >= n || b < 0 || b >= m) continue;//如果越界了,就跳过
if(st[a][b]) continue;//如果已经来过了,就跳过
//记得是t.x跟t.y,不是a跟b,a跟b是他能够行走的方向上面的点,所以需要判断的是原来的点xy
if((g[t.x][t.y] >> i & 1) == 1) continue;//如果对应二进制位是1,说明不能够通过,跳过·
//所有不能通过的情况排除了,其他都是可以通过的,全部加入队列中
q[++tt] = new PII(a,b);
st[a][b] = true;
}
}
return res;
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
for (int i = 0 ; i < n ; i ++ ){
for (int j = 0 ; j < m ; j ++ ){
g[i][j] = scan.nextInt();
}
}
//cnt表示多少房间
//area表示最大面积
int cnt = 0,area = 0;
for (int i = 0 ; i < n ; i ++ ){
for (int j = 0 ; j < m ; j ++ ){
//如果这个点没来过,进行bfs
if (!st[i][j]){
area = Math.max(area,bfs(i,j));//每一次比较一下房间的大小
cnt ++ ;//统计有多少个房间
}
}
}
System.out.println(cnt);
System.out.println(area);
}
}
class PII{
int x,y;
public PII(int x,int y){
this.x = x;
this.y = y;
}
}