递归 DFS 函数，查看二进制矩阵中的某个位置是否为 1，并且其行和列中的所有其他元素是否为 0

Question

我正在研究LeetCode 1582。二进制矩阵中的特殊位置< /a>.我怎样才能创建一个使用递归和DFS来返回特殊位置数量的函数一个 mx n 二进制矩阵。如果 matrix[i][j] == 1 并且行 中的所有其他元素，则位置 (i, j) 被称为特殊 >i 和列 j 为 0（行和列从 0 开始索引）。

示例 1

Input: mat = [[1,0,0],[0,0,1],[1,0,0]]
Output: 1
Explanation: (1, 2) is a special position because mat[1][2] == 1 and all other elements in row 1 and column 2 are 0.

示例 2

Input: mat = [[1,0,0],[0,1,0],[0,0,1]]
Output: 3
Explanation: (0, 0), (1, 1) and (2, 2) are special positions.

这是我到目前为止所拥有的，但鉴于此问题，我对如何正确执行 DFS 递归感到困惑。

class Solution:
    def numSpecial(self, mat: List[List[int]]) -> int:
        count = 0
        for ir, rval in enumerate(mat):
            for ic, cval in enumerate(rval):
                if cval == 1:
                    if self.dfs([ir, ic], mat):
                        count += 1
        return count

                        
    def dfs(self, idx, mat):
        if self.isvalid(idx, mat):
            if mat[idx[0]][idx[1]] != 0:
                return False
            else:
                north = [idx[0]-1, idx[1]]
                self.dfs(north)
                south = [idx[0]+1, idx[1]]
                self.dfs(south)
                east = [idx[0], idx[1]+1]
                self.dfs(east)
                west = [idx[0], idx[1]-1]
                self.dfs(west)
                return True # dont know if and where I should put this return True
        
    
    def isvalid(self, idx, mat):
        if idx[0] in range(0,len(mat)):
            if idx[1] in range(0,len(mat[0])):
                return True
        return False
        

另外，我知道有很多更简单的方法可以解决这个问题，但我只想能够使用DFS递归来解决它，就像我在上面尝试的那样

Answer 1

好的，所以这段代码可以工作。我必须添加一些东西。几个全局变量有点顽皮，但我不知道没有它们该怎么做。

其中之一就是迄今为止我们在 DFS 搜索中遇到的数量。我们希望在 DFS 完成后该值恰好为 1。这就是我们启动 DFS 的单元格。

我使用二维布尔数组来跟踪搜索已经进行的位置，否则它将永远持续下去。

请注意，我还添加了对 isvalid 例程的检查，以确保我们只考虑与我们正在检查的单元格相同的行或列中的值。

# Evil global variables
numOnesFound = 0
visited = []

class Solution:

def numSpecial(self, mat: List[List[int]]) -> int:
    global numOnesFound
    global visited
    
    count = 0
    for rowIndex, row in enumerate(mat):
        for colIndex, colValue in enumerate(row):
            if colValue == 1:
                numOnesFound = 0
                visited = [[False for x in range(len(mat[0]))] for y in range(len(mat))]
                self.dfs([rowIndex, colIndex], [rowIndex, colIndex], mat)
                if numOnesFound == 1:
                    count += 1
    return count

           


def dfs(self, startingPosition, idx, mat):
    global numOnesFound
    global visited
    
    if numOnesFound >= 2:
        return
    
    if self.isvalid(startingPosition, idx, mat):
        
        if visited[idx[0]][idx[1]]:
            return
        visited[idx[0]][idx[1]] = True

        if mat[idx[0]][idx[1]] != 0:
            numOnesFound += 1
        
        north = [idx[0]-1, idx[1]]
        self.dfs(startingPosition, north, mat)
        south = [idx[0]+1, idx[1]]
        self.dfs(startingPosition, south, mat)
        east = [idx[0], idx[1]+1]
        self.dfs(startingPosition, east, mat)
        west = [idx[0], idx[1]-1]
        self.dfs(startingPosition, west, mat)
    return
    

def isvalid(self, startingPosition, idx, mat):
    
    # Check to see if we're in the same column or same row as the startingPosition
    if idx[0] == startingPosition[0] or idx[1] == startingPosition[1]:
        # Check to see the indexes are within 0->height 0->width 
        if idx[0] in range(0,len(mat)):
            if idx[1] in range(0,len(mat[0])):
                return True
            
    return False