[LeetCode] 419. Battleships in a Board

Given an m x n matrix board where each cell is a battleship ‘X’ or empty ‘.’, return the number of the battleships on board.

Battleships can only be placed horizontally or vertically on board. In other words, they can only be made of the shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column), where k can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).

Example 1:

Input: board = [[“X”,”.”,”.”,”X”],[“.”,”.”,”.”,”X”],[“.”,”.”,”.”,”X”]]
Output: 2

Example 2:
Input: board = [[“.”]]
Output: 0

Constraints:
m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is either ‘.’ or ‘X’.

Follow up: Could you do it in one-pass, using only O(1) extra memory and without modifying the values board?

甲板上的战舰。

给你一个大小为 m x n 的矩阵 board 表示甲板，其中，每个单元格可以是一艘战舰 'X' 或者是一个空位 '.' ，返回在甲板 board 上放置的 战舰 的数量。

战舰 只能水平或者垂直放置在 board 上。换句话说，战舰只能按 1 x k（1 行，k 列）或 k x 1（k 行，1 列）的形状建造，其中 k 可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 （即没有相邻的战舰）。

思路

这个题的 followup 是问是否只扫描一遍并且不用额外空间。所以最优解思路是遍历一次 input，找出战舰的起始点。所谓的战舰起始点，就是为 X 的点，同时该点的上方和左侧的点不能为 X。这题其实是比较简单，因为如果战舰可以相邻，会更难判断。

二刷的时候这道题看了答案都不记得为什么上方和左边的点不能为 X，原因是因为每个单独的战舰是不能跟其他战舰相邻的，我们既然找的是战舰的起点，中间一定要隔开起码一个坐标的距离。

复杂度

时间O(mn)
空间O(1)

代码

Java实现

class Solution {
	public int countBattleships(char[][] board) {
		int m = board.length;
		if (m == 0) {
			return 0;
		}
		int n = board[0].length;
		int res = 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;
				}
				// 不是点也不是需要跳过的X那么就一定是一个战舰的起点X
				res++;
			}
		}
		return res;
	}
}