419.棋盘上的战舰

链接：419.棋盘上的战舰
难度：Medium
标签：深度优先搜索、数组、矩阵
简介：给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在甲板 board 上放置的 战舰 的数量。

题解 1 - typescript

• 编辑时间：2021-12-18
• 执行用时：80ms
• 内存消耗：41.1MB
• 编程语言：typescript
• 解法介绍：并查集。

class UnionFind {
  elements: number[];
  constructor(public size: number) {
    this.elements = new Array(size).fill(0).map((_, i) => i);
  }
  same(v1: number, v2: number): boolean {
    return this.find(v1) === this.find(v2);
  }
  find(v: number): number {
    return v === this.elements[v] ? v : (this.elements[v] = this.find(this.elements[v]));
  }
  union(v1: number, v2: number): void {
    const e1 = this.find(v1);
    const e2 = this.find(v2);
    if (e1 !== e2) {
      this.elements[e1] = e2;
      this.size--;
    }
  }
}
const dirs = [
  [1, 0],
  [0, 1],
  [-1, 0],
  [0, -1],
];
function countBattleships(board: string[][]): number {
  const n = board.length;
  const m = board[0].length;
  const uf = new UnionFind(n * m);
  const getIdx = (row: number, col: number) => row * m + col;
  let cnt = 0;
  for (let row = 0; row < n; row++) {
    for (let col = 0; col < m; col++) {
      if (board[row][col] !== 'X') {
        cnt++;
      } else {
        for (let i = 0; i < 4; i++) {
          const next_row = row + dirs[i][0];
          const next_col = col + dirs[i][1];
          if (
            next_row < 0 ||
            next_row >= n ||
            next_col < 0 ||
            next_col >= m ||
            board[next_row][next_col] === '.'
          )
            continue;
          uf.union(getIdx(row, col), getIdx(next_row, next_col));
        }
      }
    }
  }
  return uf.size - cnt;
}

题解 2 - typescript

• 编辑时间：2021-12-18
• 执行用时：80ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：dfs。

function setDot(board: string[][], n: number, m: number, row: number, col: number): void {
  if (row < 0 || row >= n || col < 0 || col >= m || board[row][col] === '.') return;
  board[row][col] = '.';
  setDot(board, n, m, row + 1, col);
  setDot(board, n, m, row - 1, col);
  setDot(board, n, m, row, col + 1);
  setDot(board, n, m, row, col - 1);
}
function countBattleships(board: string[][]): number {
  const n = board.length;
  const m = board[0].length;
  let ans = 0;
  for (let row = 0; row < n; row++) {
    for (let col = 0; col < m; col++) {
      if (board[row][col] === '.') continue;
      ans++;
      setDot(board, n, m, row, col);
    }
  }
  return ans;
}

题解 3 - typescript

• 编辑时间：2021-12-18
• 执行用时：72ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：每次遍历只统计每个战舰左上角的 X。

function countBattleships(board: string[][]): number {
  const n = board.length;
  const m = board[0].length;
  let ans = 0;
  for (let row = 0; row < n; row++) {
    for (let col = 0; col < m; col++) {
      if (
        board[row][col] === '.' ||
        (row > 0 && board[row - 1][col] === 'X') ||
        (col > 0 && board[row][col - 1] === 'X')
      )
        continue;
      ans++;
    }
  }
  return ans;
}

题解 4 - python

• 编辑时间：2024-06-11
• 执行用时：37ms
• 内存消耗：18.76MB
• 编程语言：python
• 解法介绍：dfs。

dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        n = len(board)
        m = len(board[0])
        res = 0
        def check(i: int, j: int) -> int:
            board[i][j] = '.'
            for dir in dirs:
                ni = i + dir[0]
                nj = j + dir[1]
                if 0 <= ni < n and 0 <= nj < m and board[ni][nj] == 'X':
                    check(ni, nj)
        for i in range(n):
            for j in range(m):
                if board[i][j] == 'X':
                    res += 1
                    check(i, j)
        return res