模拟战役

思路

Flood Fill

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, -1, 1};
const double eps = 1e-6;
const int N = 100 + 10;
int n, m;
char g1[4][N], g2[4][N];
bool st1[8][N], st2[8][N];

int bfs(char g[4][N], int s, int t, bool st[][N])
{
    int res = 1;
    queue<PII> qu;
    qu.push({s, t});
    st[s][t] = true;

    while (!qu.empty())
    {
        auto t = qu.front();
        qu.pop();
        int a = t.first, b = t.second;
        for (int i = -1; i <= 1; i++)
        {
            for (int j = -1; j <= 1; j++)
            {
                int x = a + i, y = b + j;
                if (x < 0 || x >= 4 || y < 0 || y >= m)
                    continue;
                if (st[x][y])
                    continue;
                st[x][y] = true;
                if (g[x][y] == '.')
                    continue;
                res++;
                qu.push({x, y});
            }
        }
    }
    return res;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> m;

    // 司机
    for (int i = 0; i < 4; i++)
    {
        cin >> g2[i];
    }

    // 齐齐
    for (int i = 0; i < 4; i++)
    {
        cin >> g1[i];
    }

    vector<int> driver, qiqi;

    // 齐齐
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!st1[i][j] && g1[i][j] == '*')
            {
                qiqi.push_back(bfs(g1, i, j, st1));
            }
        }
    }

    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!st2[i][j] && g2[i][j] == '*')
                driver.push_back(bfs(g2, i, j, st2));
        }
    }

    sort(qiqi.begin(), qiqi.end());
    sort(driver.begin(), driver.end(), [](const int &a, const int &b)
         { return a > b; });

    if (qiqi.size() >= driver.size())
    {
        int ans = 0;
        for (int i = driver.size() - 1; i < qiqi.size(); i ++)
        {
            ans += qiqi[i];
        }
        cout << ans << '\n';
    }
    else
    {
        cout << -1 << '\n';
    }
    return 0;
}