1098. 城堡问题 题解

题目描述

avatar avatar

解题思路

本题用flood fill办法求解，而最关键的是如何判断能不能从某一格走到另一个

对于每个位置上的数都可以用二进制表示其中1代表西墙，2代表北墙，4代表东墙，8代表南墙例子：如果给出3，则二进制表示为0011，说明有西墙和北墙也就是如果某位为1，则对应有墙可以对每个数用x >> i & 1来看这位是否是1，如果是1则跳过

代码

cpp

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 55;

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

int bfs(int sx, int sy)
{
    
    queue<PII>q;
    q.push({sx, sy});
    vis[sx][sy] = true;
    int area = 0;
    
    while (q.size())
    {
        auto t = q.front();
        area++; 
        q.pop();
        
        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 (g[t.x][t.y] >> i & 1 || vis[a][b])  continue;
            
            q.push({a, b});
            vis[a][b] = 1; 
        }
    }
    return area;
}

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 cnt = 0, area = 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (!vis[i][j])
            {
                area = max(area, bfs(i, j));
                cnt++;
            }
    
    printf("%d\n%d", cnt, area);
    return 0;
}

题目描述 ​

解题思路 ​

代码 ​

题目描述

解题思路

代码