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

Question

我正在研究 LeetCode 1582. Special Positions in a Binary Matrix。我如何制作一个使用 recursion 和 DFS 的函数来 return 计算 [=35 的数量=]特殊位置在m x n二进制矩阵中。位置 (i, j) 被称为 special 如果 matrix[i][j] == 1 并且行 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

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

Recursive DFS function that looks if a position in a binary matrix has a 1 and all other elements in its row and column have 0

python

recursion

matrix

depth-first-search