Python 3 DFS Solution O(n)


#1
def dfs(A,visited,curr):
    for val_i,val_j in [(-1,0),(0,-1),(1,0),(0,1)]:
        next_i,next_j = (curr[0]+val_i,curr[1]+val_j)
        if 0<=next_i<len(A) and 0<=next_j<len(A[0]) and A[next_i][next_j] == "X" and visited[next_i][next_j]==0:
            visited[next_i][next_j] = 1
            dfs(A,visited,(next_i,next_j))
        

def nextblack(A,visited,prev):
    for i in range(prev[0],len(A)):
        for j in range(len(A[0])):
            if A[i][j]=="X" and visited[i][j]==0:
                return [i,j]
    return False


class Solution:
    def black(self, A):
        g_count = 0
        visited = [[0]*len(A[0]) for _ in range(len(A))]
        present = (0,0)
        while True:
            curr = nextblack(A,visited,present)
            if curr:
                visited[curr[0]][curr[1]] = 1
                dfs(A,visited,curr)
            else:
                break
            g_count += 1
            present = curr
        return g_count