419. 甲板上的战舰

快评

题目的背景是海战棋：http://zh.battleship-game.org/

解题思路

1. 先从左到右逐行扫描，遇到无相邻行区域（连续1格或更多）则计入1艘军舰，注意处理边缘；
2. 先从上到下逐列扫描，遇到无相邻行区域（连续2格或更多，因为1格的情况已经在第1点计入过，所以不能重复计算）则计入1艘军舰，注意处理边缘；

时间复杂度O(N)，N=m*n（矩形面积）；空间复杂度O(1)，常数空间即可处理。

还有一种更快的一次扫描做法：枚举起点，符合题意的军舰左上角必为空（超出棋盘亦视为空）。

代码

func countBattleships(board [][]byte) int {
    result := 0
    count := 0

    in_ship := false
    for i, row := range board{
        for j := range row{
            if (board[i][j]=='X') && (i-1<0||board[i-1][j]=='.') && (i+1==len(board)||board[i+1][j]=='.'){
                if in_ship==false{
                    in_ship=true
                }
            }else{
                if in_ship==true{
                    in_ship=false
                    result++
                }
            }
        }
        if in_ship==true{
            result++
        }
        in_ship=false
    }

    for j:=0;j<len(board[0]);j++{
        for i:=0;i<len(board);i++{
            if (board[i][j]=='X') && (j-1<0||board[i][j-1]=='.') && (j+1==len(board[0])||board[i][j+1]=='.'){
                if in_ship==false{
                    in_ship=true
                }
                count++
            }else{
                if in_ship==true{
                    in_ship=false
                    if count>1{
                        result++
                    }
                    count=0
                }
            }
        }
        if in_ship==true && count>1{
            result++
        }
        in_ship=false
        count=0
    }

    return result
}