算法提高课汇总

模型抽象

• 4联通, 求联通块数目及最大连通块的顶点数.

• 注意门🚪的二进制运算: 方向与门🚪的二进制匹配.

具体实现

#include <iostream>

#define x first
#define y second

using namespace std;

const int N = 55;

typedef pair<int, int> pii;

int n, m;
int g[N][N];
pii q[N * N];
bool st[N][N];

int bfs(int sx, int sy)
{
    static int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};

    int tt = 0, hh = 0;
    q[tt ++] = {sx, sy};
    st[sx][sy] = true; //入队时更新st

    int res = 0; //联通块顶点个数 -> 顶点出队次数
    while( hh < tt )
    {
        res ++;
        pii cur = q[hh ++];
        int x = cur.x, y = cur.y;
        for( int i = 0; i < 4; i ++ )
        {
            int nx = x + dx[i], ny = y + dy[i];
            if( nx < 0 || nx >= n || ny < 0 || ny >= m )    continue;
            if( st[nx][ny] || (g[x][y] >> i & 1) )  continue;

            st[nx][ny] = true;
            q[tt ++] = {nx, ny};
        }
    }
    return res;
}

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

    //flood fill
    int cnt = 0, res = 0;
    for( int i = 0; i < n; i ++ )
        for( int j = 0; j < m; j ++ )
            if( !st[i][j] )
            {
                cnt ++;
                res = max(res, bfs(i, j));
            }
    cout << cnt << endl << res << endl;

    return 0;
}