AcWing 1098. 城堡问题

深碍√TFBOYSˉ_ 2024-04-08 12:55 68阅读 0赞

## AcWing 1098. 城堡问题 ##

### 原题链接 ###

[AcWing 1098. 城堡问题][AcWing 1098.]

### 算法标签 ###

BFS

### 样例解释 ###

![在这里插入图片描述][7b2949cb76734a6c93771efaebcd0c70.png]

### 思路 ###

从前向后遍历， 若该位置四面相邻位置无墙， 即存在连通关系， 将连通位置入队  
判断某一方向是否有墙判断数字第i位2进制数是否为1  
例如i为0 否数字第i位2进制数是为1 说明该位置西面有墙

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>b;--i)
    #define x first
    #define y second
    using namespace std;
    typedef pair<int, int> PII; 
    const int N=55, M=N*N;
    int m,n;
    int g[N][N];
    PII q[M];
    bool st[N][N];
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    int dfs(int sx, int sy){
        int dx[4]={0, -1, 0, 1}, dy[4]={-1, 0, 1, 0};
        int hh=0, tt=0, area=0;
        q[0]={sx, sy};
        st[sx][sy]=true;
        while(hh<=tt){
            PII t=q[hh++];
            area++;
            rep(i, 0, 4){
                int x=t.x+dx[i], y=t.y+dy[i];
                if(x<0||x>=m||y<0||y>=n){
                    continue;
                }
                if(st[x][y]){
                    continue;
                }
                // 是否有墙
                if(g[t.x][t.y]>>i&1){
                    continue;
                }
                q[++tt]={x, y};
                st[x][y]=true;
            }
        }
        return area;
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
    	m=read(), n=read();
    	rep(i, 0, m){
    	    rep(j, 0, n){
    	        g[i][j]=read();
    	    }
    	}
    	int area=0, cnt=0;
    	rep(i, 0, m){
    	    rep(j, 0, n){
    	        if(!st[i][j]){
    	            area=max(area, dfs(i, j));
    	            cnt++;
    	        }
    	    }
    	}
    	printf("%lld\n", cnt);
    	printf("%lld\n", area);
    	return 0;
    }

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 1098.]: https://www.acwing.com/problem/content/1100/
[7b2949cb76734a6c93771efaebcd0c70.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/cf1ee2f202a64be9a27bd510b2f45fe3.png
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/27215b42bb674cf09bbdf5a51dc6bb28.png