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

首先想到的是DFS方法，如下

class Solution(object):
    def countBattleships(self, board):
        """
        :type board: List[List[str]]
        :rtype: int
        """
        vs = []
        h = len(board)
        v = len(board[0])
        ans = 0
        if h is None: 
            return 0
    
        def dfs(x,y):
            for dx,dy in zip((1,0,-1,0),(0,1,0,-1)):
                nx = x+dx
                ny = y+dy
                if 0<=nx<h and 0<=ny<v:
                    if (nx, ny) not in vs and board[nx][ny] == 'X':
                        vs.append((nx,ny))
                        dfs(nx,ny)
        
    
        for i in range(0,h):
            for j in range(0,v):
                if (i,j) not in vs and board[i][j] == 'X':
                    ans += 1
                    vs.append((i,j))
                    dfs(i,j)
        return ans

然而，超时了。想了想，有些地方重复了两次，完全没必要，我们只要保证X的左边和上面没有X就OK，
所以换成下面的：

class Solution(object):
    def countBattleships(self, board):
        """
        :type board: List[List[str]]
        :rtype: int
        """
        v = len(board)
        h = len(board[0])
        ans = 0
        if v is None: 
            return 0
        for i in range(0,v):
            for j in range(0,h):
                if i == 0 and j == 0 and board[i][j] == 'X': 
                    ans += 1
                if i == 0 and j>=1:
                    if board[0][j] == 'X' and board[0][j-1] == '.':
                        ans += 1
                if j == 0 and i>=1:
                    if board[i][0] == 'X' and board[i-1][0] == '.':
                        ans += 1
                if i >=1 and j >=1:
                    if board[i][j] == 'X' and board[i-1][j] == '.' and board[i][j-1] =='.':
                        ans +=1
                        
        return ans

AC
主要学习了一下深度优先搜索，这个好久没看过了，有些细节记不太清了