海战(Sea Battle) 题解

思路分析

两艘轴对齐矩形船只不发生上下左右接触，等价于图中每一个 # 的四连通块都恰好填满其最小外接矩形（或者等价于不存在任何一个 $2 \times 2$ 子网格恰好包含 $3$ 个 # 和 $1$ 个 .）。先检查所有 $2 \times 2$ 子网格排除非法摆放（输出 Bad placement.），再用 BFS 统计 # 的四连通块个数 $S$，输出 There are S ships. 即可。时间复杂度 $O(RC)$。

参考代码

#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;

string gridArr[1005];
bool vis[1005][1005];
const int DR[4] = {-1, 1, 0, 0};
const int DC[4] = {0, 0, -1, 1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int R, C;
    if (!(cin >> R >> C)) return 0;
    for (int i = 0; i < R; ++i) cin >> gridArr[i];

    for (int i = 0; i + 1 < R; ++i)
    {
        for (int j = 0; j + 1 < C; ++j)
        {
            int cnt = (gridArr[i][j] == '#') + (gridArr[i + 1][j] == '#')
                    + (gridArr[i][j + 1] == '#') + (gridArr[i + 1][j + 1] == '#');
            if (cnt == 3)
            {
                cout << "Bad placement.\n";
                return 0;
            }
        }
    }

    int ships = 0;
    queue<pair<int, int>> q;
    for (int i = 0; i < R; ++i)
    {
        for (int j = 0; j < C; ++j)
        {
            if (gridArr[i][j] == '#' && !vis[i][j])
            {
                ++ships;
                vis[i][j] = true;
                q.push({i, j});
                while (!q.empty())
                {
                    auto cur = q.front();
                    q.pop();
                    for (int d = 0; d < 4; ++d)
                    {
                        int ni = cur.first + DR[d], nj = cur.second + DC[d];
                        if (ni >= 0 && ni < R && nj >= 0 && nj < C && gridArr[ni][nj] == '#' && !vis[ni][nj])
                        {
                            vis[ni][nj] = true;
                            q.push({ni, nj});
                        }
                    }
                }
            }
        }
    }
    cout << "There are " << ships << " ships.\n";
    return 0;
}