419. Battleships in a Board（计算甲板上的军舰数）

秒速五厘米 2022-07-15 05:46 108阅读 0赞

Given an 2D board, count how many different battleships are in it. The battleships are represented with `'X'`s, empty slots are represented with `'.'`s. You may assume the following rules:

*  You receive a valid board, made of only battleships or empty slots.
 *  Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape `1xN` (1 row, N columns) or`Nx1` (N rows, 1 column), where N can be of any size.
 *  At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.

Example:

X..X
    ...X
    ...X

In the above board there are 2 battleships.

Invalid Example:

...X
    XXXX
    ...X

This is an invalid board that you will not receive - as battleships will always have a cell separating between them.

Follow up:

Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?

题目大意：水平方向或者竖直方向上的'X'集合算一条军舰，不能拐弯，不会出现两条军舰挨着的情况。

思路：

解法一、一种解法是深度优先遍历，用两层循环对所有位置进行遍历，遇到没被访问过的‘X’则军舰数加1，然后从该点开始进行深度优先遍历，将代表该军舰的所有‘X’标记为访问过的状态。

解法二、题目进阶要求一次遍历完，并且使用O(1)的空间复杂度，那么就不能像解法一那样再声明一个记录访问标志的二维数组。我们可以通过军舰的起点计算军舰数，所谓起点，就是指一条军舰上最左边的那个‘X’或者最上面的那个‘X’。

解法一：DFS(6ms，beats 12.59%)

public class Solution {
        
        private int[] di = { -1, 0, 1, 0 }, dj = { 0, -1, 0, 1 };
        
        public int countBattleships(char[][] board) {
            int res = 0, height = board.length, width = board[0].length, i, j, m, n;
    		boolean[][] visited = new boolean[height][width];
    		for (i = 0; i < height; i++)
    			for (j = 0; j < width; j++)
    				visited[i][j] = false;
    		for (i = 0; i < height; i++)
    			for (j = 0; j < width; j++) {
    				if (board[i][j] == 'X' && visited[i][j] == false) {
    					res++;
    					DFS(board, visited, i, j, height, width);
    				}
    			}
    		return res;
        }
        
        public void DFS(char[][] board, boolean[][] visited, int i, int j,
    			int h, int w) {
    		int ii, jj, k;
    		visited[i][j] = true;
    		for (k = 0; k < 4; k++) {
    			ii = i + di[k];
    			jj = j + dj[k];
    			if (ii >= 0 && ii < h && jj >= 0 && jj < w && board[ii][jj] == 'X'
    					&& visited[ii][jj] == false)
    				DFS(board,visited,ii,jj,h,w);
    		}
    	}
    }

解法二：计算军舰起点数（3ms，beats 93.6%）

public class Solution {
        public int countBattleships(char[][] board) {
            int res = 0, height = board.length, width = board[0].length, i, j;
    		for (i = 0; i < height; i++)
    			for (j = 0; j < width; j++) {
    				if (board[i][j] == '.' || (i > 0 && board[i - 1][j] == 'X')
    						|| j > 0 && board[i][j - 1] == 'X')
    					continue;
    				res++;
    			}
    		return res;
        }
    }