Runtime Error for maximum recursion depth. How can I optimize my code?


  • 0
    A

    It indicates Line 31: RuntimeError: maximum recursion depth exceeded in cmp.
    How can I optimize my code?

    class Solution:
    # @param {character[][]} board
    # @return {void} Do not return anything, modify board in-place instead.
    def solve(self, board):
        m = len(board)
        if m != 0:
            n = len(board[0])
            
            self.visit = []
            for i in range(m):
                self.visit.append([False] * n)
                
            for i in range(n):
                if not self.visit[0][i]:
                    self.dfs(board, 0, i, m, n)
                if not self.visit[m-1][i]:
                    self.dfs(board, m-1, i, m, n)
                
            for i in range(m):
                if not self.visit[i][0]:
                    self.dfs(board, i, 0, m, n)
                if not self.visit[i][n-1]:
                    self.dfs(board, i, n-1, m, n)
            
            for i in range(m):
                for j in range(n):
                    if not self.visit[i][j]:
                        board[i][j] = 'X'
    
    def dfs(self, board, i, j, m, n):
        if board[i][j] == 'X' or self.visit[i][j]:
            return
        
        self.visit[i][j] = True
        
        if i > 0 and not self.visit[i-1][j]:
            self.dfs(board, i-1, j, m, n)
            
        if i < m-1 and not self.visit[i+1][j]:
            self.dfs(board, i+1, j, m, n)
            
        if j > 0 and not self.visit[i][j-1]:
            self.dfs(board, i, j-1, m, n)
            
        if j < n-1 and not self.visit[i][j+1]:
            self.dfs(board, i, j+1, m, n)

  • 0

    If you look at the test case, you'll see that it's a zig-zag-line with length > 30000. Python usually has a recursion limit of 1000. I believe the OJ here at least sometimes increases that limit. You can try increasing it yourself with sys.setrecursionlimit, but it's unsafe. You'll likely have to give up this recursive approach or switch to another language.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.