leetcode | go | 第419题 | 甲板上的战舰

甲板上的战舰

go

解决思路

1. dir 为可移动的方向，m、n 为数组行数和列数
2. dfs 参数 i、j 当前位置（只会遍历值为 X 的位置）
3. 将该位置的值该为 '.'，遍历可能的方向，在不越界且新位置的值为 'X' 的情况下，dfs 新位置（将和当前位置 X 连通的所有 X 都消除）
4. ans 为 0，遍历整个数组，如果值为 X，ans++，遍历该位置
5. return ans
6. 空间不太好
7. 题解思路：（1）遍历扫描（2）枚举起点

相关问题

1. 这道题和第 200 题比较类似
2. 不要把名字搞混了

var dirs = [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
func countBattleships(board [][]byte) int {
    m,n:=len(board),len(board[0])
    var dfs func(i,j int)
    dfs=func(i,j int){
        board[i][j]='.'
        for _, d := range dirs {
            x,y:=i+d[0],j+d[1]
            if x>=0 && x<m && y>=0 && y<n && board[x][y]=='X' {
                dfs(x,y)
            }
        }
    }
    ans:=0
    for i,f:=range board {
        for j,_:=range f {
            if board[i][j]=='X' {
                ans++
                dfs(i,j)
            }
        }
    }
    return ans
}