Author: lvvj
Date: 20250823
tag: 广度优先搜索
link: https://www.luogu.com.cn/problem/P1331

题目描述

link

分析

略

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
char g[N][N];
int n, m, cnt;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    g[x][y] = '.';

    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();

        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 (g[nx][ny] != '#') continue;
            q.push({nx, ny});
            g[nx][ny] = '@';
        }
    }
}

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

    // 检查是否船只位置是否合法
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m - 1; j++) {
            int cnt = 0;
            cnt += g[i][j] == '#';
            cnt += g[i][j + 1] == '#';
            cnt += g[i + 1][j] == '#';
            cnt += g[i + 1][j + 1] == '#';
            if (cnt == 3) {
                cout << "Bad placement.";
                return 0;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == '#') {
                cnt++;
                bfs(i, j);
            }
        }
    }

    cout << "There are " << cnt << " ships." << endl;

    return 0;
}