AcWing 1098. 城堡问题

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

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

作者：

zzw1 , 2020-01-21 10:43:58 , 所有人可见 , 阅读 6110

31

5

城堡问题.png

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std ;

typedef pair<int,int> PII ;
const int N = 50 ;

int g[N][N] ;
int dist[N][N] ;
int dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0} ;
int n,m ;

int bfs(int x,int y){
    dist[x][y] = 0 ;
    queue<PII> q ;
    q.push({x,y}) ;

    int cnt = 0 ;
    while(q.size()){
        PII ele = q.front() ;
        q.pop() ;
        cnt ++ ;
        int x = ele.first, y = ele.second ;
        for(int i=0;i<4;i++){
            if(!(g[x][y]>>i&1)){
                int a = x + dx[i],b = y + dy[i] ;
                if(dist[a][b] == -1){
                    dist[a][b] = dist[x][y] + 1 ;
                    q.push({a,b}) ;
                }
            }
        }
    }
    return cnt ;
}

int main(){
    scanf("%d%d",&n,&m) ;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf("%d",&g[i][j]) ;
        }
    }

    int res = 0,maxv = 0 ;
    memset(dist,-1,sizeof dist) ;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(dist[i][j] == -1){
                res ++ ;
                maxv = max(maxv,bfs(i,j)) ;
            }
        }
    }
    printf("%d\n",res) ;
    printf("%d\n",maxv) ;

    return 0 ;
}

42 评论

너 7个月前

tql，根本没有想到二进制的方法

baikun 9个月前

房子最外围一定有墙所以判断出界的那一步可以省掉这是一个细节

ACMaster 2021-06-05 10:36

%%%

WEN@123 2021-03-29 09:33

能想到二进制，很牛皮

云寄_9 2023-11-04 20:08

想问一下就是最开始初始化以后第一个点(0,0)必然会进bfs，但是如果0，0点是墙，周围也都是墙的话，按照代码他也会先进队列，然后在pop之后让cnt=1返回，但是这样是并不会有房间应该为0啊，而且这样也会增加一个房间的个数

云寄_9 2023-11-04 20:18

上面说错了不是cnt=1,是area=1；就是第一个点st肯定是0那就肯定会进bfs的，如果0,0这个点旁边都有墙那岂不是每次返回area=1，然后cnt也一直加加加。这里搞不明白，有没有佬能教教

指尖上的的青春 2023-05-08 20:43

大佬，可以帮我看一下吗

// ------------------------------- ？？ -------------------------------

//对于每一个数可以拆分成二进制，如果当前数左移i位&1不为零，则可以向这个方向继续深搜，直到枚举所有情况
#include <iostream>
#include <cstring>
#include<algorithm>
#include<cstring>

using namespace std;
const int N = 55,M=N*N;
int a[N][M],n,m;
bool st[N][M];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

int dfs(int x,int y)
{
    st[x][y]=true;
    int q,t;
    int ans=1;
    for(int i=0;i<4;i++)
    {
        q=dx[i]+x,t=dy[i]+y;
        //cout<<q<<" "<<t<<endl;
        if(!st[q][t] && (!a[x][y]>>i&1))
        {
            ans+=dfs(q,t);
        }
    }
    return ans;
}

int main()
{
    cin>>n>>m;
    int res=0,sum=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>a[i][j];
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(!st[i][j])
                res++;
                sum=max(sum,dfs(i,j));
                //cout<<sum<<endl;
        }
    }
    cout<<res<<endl<<sum;

    return 0;
}

baikun 9个月前

你忘记判断q和t是否出界了

baikun 9个月前回复了 baikun 的评论

根据这道题题意房子最外围一定有墙是可以不需要判断q t是否出界的但你需要把 if(!(g[x][y]>>i&1))放到前面

jatro13 2022-10-22 20:33

dist 代表什么？

Zzint 2022-10-26 11:08

这里的dist是判重的作用，dist初始化为-1，走过的点的dist值会一直增加，dist的最后一个值d[n][n]就是记录的面积,但是走到最后的二维坐标不知道，所以只有判重的作用可以用布尔数组替代

jatro13 2022-10-26 20:43 回复了 Zzint 的评论

哦，谢谢！

牧濑红莉栖 2022-08-11 15:15

大佬为什么这道题目用dfs求连通块都是错的
能看一下嘛

#include <iostream>

using namespace std;

const int N = 55;
int n, m;
int g[N][N];
bool st[N][N];
int ans = 1;

int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0};

void dfs (int x, int y) {
    st[x][y] = true;

    for (int i = 0; i < 4; ++ i) {
        int a = dx[i] + x, b = dy[i] + y;
        if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) continue;
        if (g[x][y] >> i & 1) continue;
        dfs(a, b);
    }
}

int main () {
    cin >> n >> m;

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            cin >> g[i][j];

    int ans = 0;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            if (!st[i][j]) {
                dfs(i, j);
                ++ ans;
            }

    cout << ans << endl;

    return 0;
}