【LeetCode】419. デッキ上の戦艦結題報告(python)

原題住所:https://leetcode-cn.com/problems/battleships-in-a-board/
タイトルの説明:
2次元のデッキを指定し、その中に何隻の戦艦があるかを計算してください.戦艦は'X'で表示され、空席は'.'に表示されます.次のルールを遵守する必要があります.
有効なデッキをあげます.戦艦か空席だけで構成されています.戦艦は水平または垂直にしか置けない.言い換えれば、戦艦は1 xN(1行、N列)またはNx 1(N行、1列)のみで構成され、そのうちNは任意の大きさであってもよい.2隻の戦艦の間には少なくとも水平または垂直の空席が隔てられている.すなわち、隣接する戦艦はない.例:
X..X ...X ...Xは上のデッキに戦艦が2隻あります.
無効なサンプル:
...X XXXX ...Xはこのような無効な甲板を受け取ることはありません.戦艦の間には少なくとも空席があるので、それらを分けます.
ステップ:
O(1)の余分な空間だけを1回のスキャンアルゴリズムで使用し、デッキの値を変更せずにこの問題を解決できますか?
 
問題解決方案:
深度は優先的に巡回されますが、元の配列は変更されます.

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        m = len(board)
        if m == 0:
            return 0
        n = len(board[0])
        if n == 0:
            return 0
        res = 0    
        
        def dfs(x, y):
            dx = [1, -1, 0, 0]
            dy = [0, 0, 1, -1]
            
            for k in range(4):
                xx = x + dx[k]
                yy = y + dy[k]
                
                if 0 <= xx < m and 0 <= yy < n and board[xx][yy] == "X":
                    board[xx][yy] = "."
                    dfs(xx, yy)
                    
        for i in range(m):
            for j in range(n):
                if board[i][j] == "X":
                    board[i][j] = "."
                    dfs(i, j)
                    res += 1
                    
        return res

配列を変更しない:

class Solution:
    def countBattleships(self, board: List[List[str]]) -> int:
        rows = len(board)
        cols = len(board[0])
        cnt = 0
        for i in range(rows):
            for j in range(cols):
                if board[i][j] == 'X':
                    if (i - 1 < 0 or board[i - 1][j] != 'X') and (j - 1 < 0 or board[i][j - 1] != 'X'):
                        cnt += 1
        return cnt