AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 校园
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

AcWing 1098. 城堡问题    原题链接    简单

作者: 作者的头像   栗子ing ,  2022-05-14 16:09:19 ,  所有人可见 ,  阅读 17


2


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;
    }
}

0 评论

你确定删除吗?
1024
x

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息