文字教学

这道题需要同时验证两个条件：所有船只都是方形且船只之间互不接触，用BFS（广度优先搜索）解决：

1. 找连通块：遍历棋盘，遇到未访问的#就用BFS找出整个连通块，记录该块的最小/最大行号、最小/最大列号和#的数量。
2. 验证方形：若连通块是方形，其#的数量必须等于“(最大行-最小行+1) × (最大列-最小列+1)”的矩形面积。
3. 验证不接触：检查该方形的“外围一圈”（行和列各向外扩展1格），若存在其他#，说明船只接触，布局不合法。
4. 若所有连通块都通过验证，统计船只数量并输出。

代码

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

const int N = 1005;
char g[N][N];
bool vis[N][N];
int R, C;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C;
    for (int i = 0; i < R; ++i) {
        cin >> g[i];
    }
    int S = 0;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            if (g[i][j] == '#' && !vis[i][j]) {
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                vis[i][j] = true;
                int min_r = i, max_r = i, min_c = j, max_c = j, cnt = 0;
                while (!q.empty()) {
                    pair<int, int> cur = q.front();
                    q.pop();
                    int x = cur.first, y = cur.second;
                    cnt++;
                    min_r = min(min_r, x);
                    max_r = max(max_r, x);
                    min_c = min(min_c, y);
                    max_c = max(max_c, y);
                    for (int d = 0; d < 4; ++d) {
                        int nx = x + dx[d], ny = y + dy[d];
                        if (nx >= 0 && nx < R && ny >= 0 && ny < C && g[nx][ny] == '#' && !vis[nx][ny]) {
                            vis[nx][ny] = true;
                            q.push(make_pair(nx, ny));
                        }
                    }
                }
                // 检查是否为方形
                int area = (max_r - min_r + 1) * (max_c - min_c + 1);
                if (area != cnt) {
                    cout << "Bad placement." << endl;
                    return 0;
                }
                // 检查外围是否有其他船
                for (int x = min_r - 1; x <= max_r + 1; ++x) {
                    for (int y = min_c - 1; y <= max_c + 1; ++y) {
                        if (x >= 0 && x < R && y >= 0 && y < C) {
                            if (!(x >= min_r && x <= max_r && y >= min_c && y <= max_c)) {
                                if (g[x][y] == '#') {
                                    cout << "Bad placement." << endl;
                                    return 0;
                                }
                            }
                        }
                    }
                }
                S++;
            }
        }
    }
    cout << "There are " << S << " ships." << endl;
    return 0;
}