棋盘上的战舰 图解题解

棋盘上摆着 X 和空位，这道题要数出几艘船

给一个 m×n 的棋盘 board，每格要么是战舰的一段 X、要么是空位点。战舰只能横排成 1×k 或竖排成 k×1 的一条直线，且任意两艘之间至少隔一个空格、绝不挨着。返回一共有几艘战舰。题面那张棋盘的答案是 2：左上角 (0,0) 一艘单格船，最右一列 (0,3)、(1,3)、(2,3) 连成一艘竖排三格船。

把整艘船找出来再数，多花的是哪一笔

一个直觉做法是对每个还没数过的 X 做一次 DFS，顺着连通的格子一路铺开、把整艘船都标记掉，铺开几次就是几艘船。答案没错，但每铺一次都要开访问标记数组、或往递归栈里压一串格子，额外空间涨到 O(m·n)。而这题的进阶要求偏偏是只用 O(1) 额外空间、还不许改动原棋盘，染色法两条都踩线。

既然每艘船都是直线，何必把它整条走完

换个数法：不找整艘船，只找每艘船左上角那一格。横排船的最左格、竖排船的最上格就是它的「船头」，每艘船有且只有一个船头，数船头就等于数船。怎么认船头？看这个 X 的正上方和正左方：上、左都不是 X，说明前面没有同船的格子接着，它就是船头，计一次数；只要上或左有一个是 X，它就是后半截，跳过。之所以不重不漏，全靠「任意两艘至少隔一格」：船与船不相邻，一个 X 的上、左邻居只可能是同船的格子、绝不会牵到隔壁船，「上左都不是 X」就精准卡住了每艘船唯一的那个头。

一行一行扫过去，每个 X 只做一道判断题

扫描顺序是从上到下、每行从左到右。碰到空位点直接跳过；碰到 X，就做那道判断题：它上边一格（同列上一行）、左边一格（同行左一列）是不是 X。两个都不是 X，船头计数加一；只要有一个是 X，跳过。第 0 行的 X 上方是棋盘外、第 0 列的 X 左方是棋盘外，都视作那侧不是 X。全程只养一个计数器，扫完它就是答案。

回到题面这张 3×4 棋盘，逐格数船头

board=[[X,.,.,X],[.,.,.,X],[.,.,.,X]]，三行四列。(0,0) 是 X，上左都在界外，判成船头，计数到 1。(0,1)、(0,2) 空位跳过。(0,3) 是 X，上方界外、左方 (0,2) 是空位，又一个船头，计数到 2。(1,0) 到 (1,2) 空位跳过；(1,3) 是 X，上方 (0,3) 也是 X，是后半截，跳过。(2,0) 到 (2,2) 空位跳过；(2,3) 是 X，上方 (1,3) 也是 X，跳过。扫完全盘，计数器停在 2，也就是那艘单格船加一艘竖排三格船。

漏看左方那一列，横排战舰会被数成好几艘

每个格子只访问一次、外加常数次上左判断，时间 O(m·n)；只用一个计数变量、不开数组也不写回棋盘，空间 O(1)，正好压在进阶要求上。两个最容易栽的地方：只查上方、忘了左方，横排船的第二格、第三格因为上方不是 X，会被逐个误判成新船头，一艘横排船数成好几艘，横排的非头格正是靠「左方是 X」才被跳过的。还有第 0 行、第 0 列的边界，直接读 board[i-1][j] 或 board[i][j-1] 会越界，得先判 i＞0、j＞0 再看邻居。空棋盘或整盘没一个 X，计数器一直是 0，返回 0。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        m, n = len(board), len(board[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if board[i][j] == '.':
                    continue
                if i > 0 and board[i - 1][j] == 'X':
                    continue
                if j > 0 and board[i][j - 1] == 'X':
                    continue
                ans += 1
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int countBattleships(vector<vector<char>>& board) {
        int m = board.size(), n = board[0].size();
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (i > 0 && board[i - 1][j] == 'X') {
                    continue;
                }
                if (j > 0 && board[i][j - 1] == 'X') {
                    continue;
                }
                ++ans;
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int countBattleships(char[][] board) {
        int m = board.length, n = board[0].length;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (i > 0 && board[i - 1][j] == 'X') {
                    continue;
                }
                if (j > 0 && board[i][j - 1] == 'X') {
                    continue;
                }
                ++ans;
            }
        }
        return ans;
    }
}