C++ works but python gets TLE


  • 0
    X

    I used the same strategy for python and C++: BFS. I used queue in C++ and deque in python for the BFS. I have also checked to make sure that I "mark" the grid while pushing in the queue, instead of "mark" it while poping it from the queue.

    But apparently C++ passed while python part gets TLE. Anybody could kindly point out what is wrong?

    class Solution:
        # @param board, a 9x9 2D array
        # Capture all regions by modifying the input board in-place.
        # Do not return any value.
        def solve(self, board):
            row=len(board)
            if(row<3):return
            col=len(board[0])
            if(col<3):return
            tmp=[0]*col;marker=[]
            for i in range(row):marker.append(tmp[:])
            self.solve_rows(board,marker,0,row,col)
            self.solve_rows(board,marker,row-1,row,col)
            self.solve_cols(board,marker,0,row,col)
            self.solve_cols(board,marker,col-1,row,col)
            for i in range(1,row-1):
                for j in range(1,col-1):
                    if(board[i][j]=='O' and marker[i][j]==0):board[i][j]='X'
                        #board[i]=board[i][:j]+'X'+board[i][j+1:]
                        
        def solve_rows(self,board,marker,i,row,col):
            for j in range(col):
                if(board[i][j]=="O" and marker[i][j]==0):
                    q=collections.deque()
                    q.append((i,j));marker[i][j]=1
                    while(q):
                        tp=q.popleft()
                        if(tp[0]>0 and board[tp[0]-1][tp[1]]=='O' and marker[tp[0]-1][tp[1]]==0):q.append((tp[0]-1,tp[1]));marker[tp[0]-1][tp[1]]=1
                        if(tp[0]<row-1 and board[tp[0]+1][tp[1]]=='O' and marker[tp[0]+1][tp[1]]==0):q.append((tp[0]+1,tp[1]));marker[tp[0]+1][tp[1]]=1
                        if(tp[1]>0 and board[tp[0]][tp[1]-1]=='O' and marker[tp[0]][tp[1-1]]==0):q.append((tp[0],tp[1]-1));marker[tp[0]][tp[1]-1]=1
                        if(tp[1]<col-1 and board[tp[0]][tp[1]+1]=='O' and marker[tp[0]][tp[1]+1]==0):q.append((tp[0],tp[1]+1));marker[tp[0]][tp[1]+1]=1
                        
        def solve_cols(self,board,marker,j,row,col):
            for i in range(row):
                if(board[i][j]=="O" and marker[i][j]==0):
                    q=collections.deque()
                    q.append((i,j));marker[i][j]=1
                    while(q):
                        tp=q.popleft()
                        if(tp[0]>0 and board[tp[0]-1][tp[1]]=='O' and marker[tp[0]-1][tp[1]]==0):q.append((tp[0]-1,tp[1]));marker[tp[0]-1][tp[1]]=1
                        if(tp[0]<row-1 and board[tp[0]+1][tp[1]]=='O' and marker[tp[0]+1][tp[1]]==0):q.append((tp[0]+1,tp[1]));marker[tp[0]+1][tp[1]]=1
                        if(tp[1]>0 and board[tp[0]][tp[1]-1]=='O' and marker[tp[0]][tp[1-1]]==0):q.append((tp[0],tp[1]-1));marker[tp[0]][tp[1]-1]=1
                        if(tp[1]<col-1 and board[tp[0]][tp[1]+1]=='O' and marker[tp[0]][tp[1]+1]==0):q.append((tp[0],tp[1]+1));marker[tp[0]][tp[1]+1]=1

Log in to reply
 

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