P1331 海战

May 8, 2026 · 6 分钟阅读 · 深度优先搜索 ·

文章目录

题目信息

字段	内容
题号	P1331
难度	蓝题
知识点	搜索、DFS、连通性

题目描述

在峰会期间，武装部队处于高度戒备。巡洋舰和舰队被派去保护海岸线。为了更好地训练，他们使用了一个海战游戏。

在一个方形的棋盘上，放置了若干艘船，每艘船都是方形的（由若干格子组成）。每艘船不能与其它船接触（上下或左右相邻的不同船视为接触，即不合法）。

给定棋盘布局（# = 船的一部分，. = 水），求出船只总数。若布局不合法，输出相应提示。

输入格式

第一行：两个整数 R C，表示棋盘的行数和列数
接下来 R 行：每行 C 个字符，为 # 或 .

输出格式

合法：There are S ships.（S 为船只数量）
非法：Bad placement.

样例

输入

6 8
.....#.#
##.....#
##.....#
.......#
#......#
#..#...#

输出

There are 5 ships.

数据范围

1 ≤ R, C ≤ 1000

解题思路

核心思想

本题分为两步：

第一步——排除非法布局： 若两艘船接触，在棋盘上一定表现为某个 2×2 方格中恰好有 3 个 #（即 L 形或反 L 形）。这是因为：

船是方形的，不允许有孤立突出
接触只能通过格子角点（斜对角）以外的方式
3 个 # 的 2×2 方格恰好是船与船接触的唯一形态

因此，遍历棋盘所有 2×2 方格，若出现 cnt == 3 的情况，直接判定非法。

第二步——计数船只： 排除非法后，棋盘上每个连通块（4 连通，# 格子群）就是一条船。

计数技巧：每艘船的"左上基准格"（该连通块中行号最小、行号相同则列号最小的格子）满足：它的上方和左方一定不是 #。反过来说，凡满足 ch[i][j]=='#' && ch[i-1][j]!='#' && ch[i][j-1]!='#' 的格子，一定是某艘船的左上基准格，一艘船恰好对应一个这样的格子。

算法步骤

读入棋盘
枚举所有 i = 1..R-1、j = 1..C-1，检查每个 2×2 方格的 # 个数；若出现 3 个，输出 Bad placement. 并结束
枚举所有格子，满足左上基准格条件的计数器 +1
输出 There are ans ships.

完整代码

C++

#include <iostream>
using namespace std;

int n, m;
char ch[1010][1010];

// 检查 (x, y) 为左上角的 2×2 方格是否合法
inline bool valid_square(int x, int y) {
    int cnt = 0;
    if (ch[x][y]     == '#') cnt++;
    if (ch[x + 1][y] == '#') cnt++;
    if (ch[x][y + 1] == '#') cnt++;
    if (ch[x + 1][y + 1] == '#') cnt++;
    return cnt != 3;   // cnt == 3 说明两船接触，非法
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> ch[i][j];
        }
    }

    // 第一步：检查所有 2×2 方格，排除非法布局
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (!valid_square(i, j)) {
                cout << "Bad placement." << '\n';
                return 0;
            }
        }
    }

    // 第二步：统计船只数量（左上基准格法）
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (ch[i][j] == '#'
                && ch[i - 1][j] != '#'
                && ch[i][j - 1] != '#') {
                ans++;
            }
        }
    }

    cout << "There are " << ans << " ships." << '\n';
    return 0;
}

关键代码讲解

2×2 方格非法检测

inline bool valid_square(int x, int y) {
    int cnt = 0;
    if (ch[x][y]         == '#') cnt++;
    if (ch[x + 1][y]     == '#') cnt++;
    if (ch[x][y + 1]     == '#') cnt++;
    if (ch[x + 1][y + 1] == '#') cnt++;
    return cnt != 3;
}

检查左上角为 (x, y) 的 2×2 方格。cnt == 3 表示 L 形或反 L 形——这是两艘船接触的唯一形态，因此直接判定非法。

左上基准格计数

if (ch[i][j] == '#'
    && ch[i - 1][j] != '#'
    && ch[i][j - 1] != '#') {
    ans++;
}

对于任意 # 格子，如果它的上方和左方都不是 #，它就是所在连通块的左上角。每个连通块（每艘船）有且仅有一个这样的格子，因此 ans 恰好等于船只数量。

为什么左上基准格恰好是一个连通块一个？
设连通块为 S，取 minRow = min(i for (i,j) in S)，再取 minCol = min(j for (i,j) in S and i == minRow)。该格子 (minRow, minCol) 的上方格子不属于 S（否则 minRow 可以更小），同理左方也不属于 S，故 (minRow, minCol) 满足条件。唯一性得证。

复杂度分析

方法	时间复杂度	空间复杂度
暴力枚举	O(R×C)	O(R×C)

检查 2×2 方格：约 (R-1)×(C-1) 次 → O(R×C)
计数：遍历全部格子 → O(R×C)
R, C ≤ 1000，约 10⁶ 次操作，轻松通过

易错点

数组下标从 1 开始：代码将输入存到 ch[1..n][1..m]，第 0 行/列为"哨兵"（自然为 .），避免了边界判断
2×2 检查范围：只需检查到 i < n, j < m，不需要额外处理越界
cnt != 3 而非 cnt == 4：cnt == 4 是正常的完整方形船（合法），cnt == 3 才非法

其他语言解法

Java

import java.io.*;

public class Main {
    static char[][] g;
    static int n, m;

    static boolean badSquare(int x, int y) {
        int cnt = 0;
        cnt += g[x][y]     == '#' ? 1 : 0;
        cnt += g[x + 1][y] == '#' ? 1 : 0;
        cnt += g[x][y + 1] == '#' ? 1 : 0;
        cnt += g[x + 1][y + 1] == '#' ? 1 : 0;
        return cnt == 3;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().trim().split("\\s+");
        n = Integer.parseInt(first[0]);
        m = Integer.parseInt(first[1]);

        g = new char[n + 2][m + 2];  // 外围一圈为 '\0'，避免越界

        for (int i = 1; i <= n; i++) {
            String line = br.readLine().trim();
            for (int j = 1; j <= m; j++) {
                g[i][j] = line.charAt(j - 1);
            }
        }

        // 第一步：检查非法接触
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (badSquare(i, j)) {
                    System.out.println("Bad placement.");
                    return;
                }
            }
        }

        // 第二步：左上基准格计数
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (g[i][j] == '#'
                    && g[i - 1][j] != '#'
                    && g[i][j - 1] != '#') {
                    ans++;
                }
            }
        }
        System.out.println("There are " + ans + " ships.");
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

func badSquare(g [][]byte, x, y int) bool {
    cnt := 0
    for _, dx := range []int{0, 1} {
        for _, dy := range []int{0, 1} {
            if g[x+dx][y+dy] == '#' {
                cnt++
            }
        }
    }
    return cnt == 3
}

func main() {
    in := bufio.NewReader(os.Stdin)

    var n, m int
    fmt.Fscan(in, &n, &m)

    // 第0行第0列留空，下标从1开始
    g := make([][]byte, n+2)
    for i := 0; i <= n+1; i++ {
        g[i] = make([]byte, m+2)
    }

    for i := 1; i <= n; i++ {
        line := make([]byte, m)
        fmt.Fscan(in, &line)
        for j := 1; j <= m; j++ {
            g[i][j] = line[j-1]
        }
    }

    // 第一步：检查 2×2 方格
    for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            if badSquare(g, i, j) {
                fmt.Println("Bad placement.")
                return
            }
        }
    }

    // 第二步：左上基准格计数
    ans := 0
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if g[i][j] == '#' && g[i-1][j] != '#' && g[i][j-1] != '#' {
                ans++
            }
        }
    }
    fmt.Printf("There are %d ships.\n", ans)
}

JavaScript

'use strict';

function solve() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
    const [n, m] = input[0].split(' ').map(Number);

    // 下标从1开始，第0行第0列为空
    const g = Array.from({ length: n + 2 }, () => Array(m + 2).fill('.'));
    for (let i = 1; i <= n; i++) {
        const line = input[i].trim();
        for (let j = 1; j <= m; j++) {
            g[i][j] = line[j - 1];
        }
    }

    // 第一步：检查 2×2 方格
    for (let i = 1; i < n; i++) {
        for (let j = 1; j < m; j++) {
            let cnt = 0;
            for (let di of [0, 1]) {
                for (let dj of [0, 1]) {
                    if (g[i + di][j + dj] === '#') cnt++;
                }
            }
            if (cnt === 3) {
                console.log('Bad placement.');
                return;
            }
        }
    }

    // 第二步：左上基准格计数
    let ans = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (g[i][j] === '#' && g[i - 1][j] !== '#' && g[i][j - 1] !== '#') {
                ans++;
            }
        }
    }
    console.log(`There are ${ans} ships.`);
}

solve();