[数据结构与算法]模拟战役(洪水漫盖)

原题

思路

• 可以看作大炮形成的八连通
• 齐齐一方每次统计连通块中大炮的数量
• 尽量先用大炮少的连通块攻击
• 若七七一方连通块数量小于司机一方，则其不可能获胜

代码

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;

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

char a[N][N], b[N][N];
PII q[N * N];
bool st[N][N];
int ca[N], cb[N];
int  m;
vector<int>u;

int bfs(int sx, int sy, int u)
{
    int res = 1;
    int hh = 0, tt = 0;
    q[0] = {sx, sy};
    st[sx][sy] = true;

    while(hh <= tt)
    {
        auto t = q[hh ++];
        for(int i = t.x - 1; i <= t.x + 1;i ++)
            for(int j = t.y - 1; j <= t.y + 1; j ++)
            {
                if(i == t.x && j == t.y) continue;
                if(i >= 4 + u || i < u || j >= m || j < 0) continue;
                if(a[i][j] == '.' || st[i][j]) continue;

                q[++ tt] = {i, j};
                st[i][j] = true;
                res ++;
            }
    }

    return res;
}

int main()
{
    cin >> m;
    int cnt = 0, cot = 0;

    for(int i = 0; i < 8; i ++) cin >> a[i];

    for(int i = 0; i < 4; i ++)
        for(int j = 0; j < m; j ++)
        {
            if(!st[i][j] && a[i][j] == '*')
            {
                bfs(i, j, 0);
                cnt ++;
            }
        }

    for(int i = 4; i < 8; i ++)
        for(int j = 0; j < m; j ++)
        {
            if(!st[i][j] && a[i][j] == '*')
            {
                u.push_back(bfs(i, j, 4));
            }
        }

    cot = u.size();
    if(cnt > cot)  puts("-1");
    else
    {
        sort(u.begin(), u.end());
        int ans = 0;
        for(int i = cnt - 1; i < cot; i ++) ans += u[i] ;
        cout << ans << endl;
    }

    return 0;
}