首页 > 代码库 > leetcode 419

leetcode 419

题目说明:

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.

 

解法1思路:

这里需要计算战舰队的数量count,可转换为计算每个战舰队位于最左上角的船只(我们称为战舰队头)。 用两个循环,对网格内的每一个格子进行遍历,若该格子为X(即有战舰),则分以下几种情况: 
若在网格的最左上角(即i=0,j=0),则存在一个舰队,count自加1; 
若在网格的最上角(即i=0),但不在最左边(即j!=0),则需要判断该位置的左边(即board[i][j-1])是否有战舰存在,若其左边不存在战舰,则该位置为战舰队头,count自加1; 
若在网格的最左边(即j=0),但不在最上边(即i!=0),则需要判断该位置的上面(即board[i-1][j])是否有战舰存在,若其上面不存在战舰,则该位置为战舰队头,count自加1; 
若战舰不在最左边也不在最上边(即i!=0且j!=0),则需要判断该战舰的左边和上面是否还有战舰存在,若其左边和上面都不存在战舰,则该位置为战舰队头,count自加1; 
其余情况,战舰都不属于战舰队头。

 

解法1代码:

int countBattleships(vector<vector<char>>& board)
{
    int counter = 0;
    for (int i = 0; i < board.size(); i ++) {
        for (int j = 0; j < board[i].size(); j ++) {
            if (board[i][j] == X) {
                if (i == 0 && j == 0)
                    counter ++;
                else if (i == 0 && j != 0 && board[i][j - 1] == .)
                    counter ++;
                else if (j == 0 && i != 0 && board[i - 1][j] == .)
                    counter ++;
                else if (i != 0 && j != 0 && board[i - 1][j] == . && board[i][j - 1] == .)
                    counter ++;
            }
            
        }
    }

    return counter;
}

 

 

解法2思路:

和解法1相似,只是这种解法是从反面分析,逐项排除非battleships的项,最后留下符合条件的项,这种剪枝策励在leetcode的算法题中非常常见。

解法2代码:

int countBattleships(vector<vector<char>>& board)
{
    int counter = 0;
    for (int i = 0; i < board.size(); i ++) {
        for (int j = 0; j < board[i].size(); j ++) {
            if (board[i][j] == .)
                continue;
            if (j > 0 && board[i][j - 1] == X)
                continue;
            if (i > 0 && board[i - 1][j] == X)
                continue;
            
            ++ counter;
        }
    }
    
    return counter;
}

 

 

部分引用自:

http://blog.5ibc.net/p/94878.html

http://blog.csdn.net/mebiuw/article/details/52876700

leetcode 419