Simple Python 3 Implementation Using DFS


#1
import numpy as np
class Solution:
    def isValidPoint(self,i,j,C,D,E,F):
        for k in range(C):
            if (E[k]-i)**2+(F[k]-j)**2<=D**2:
                return False
        return True
    
    def isinrectangle(self,i,j,A,B):
        if i<0 or j<0 or i>A or j>B:
            return False
        return True
    
    def checkAB(self,i,j,A,B):
        if i==A and j==B:
            return True
        return False
        
    def solve(self, A, B, C, D, E, F):
        Valid=np.zeros((abs(A-0)+1,abs(B-0)+1),dtype=int)
        for i in range(len(Valid)):
            for j in range(len(Valid[0])):
                if self.isValidPoint(i,j,C,D,E,F):
                    Valid[i][j]=1
        
        #for i in range(A+1):
        #    print("")
        #    for j in range(B+1):
        #        if j==0:
        #            print(" "*5,end="")
        #        print(Valid[i][j],end="")
        
        if Valid[A][B]==0:
            #print("")
            return "NO"

        s=[(0,0)]
        vis=set([(0,0)])
        i=0
        j=0
        while s:
            #print("")
            #print(i,j)
            #print(s)
            if (i,j) not in vis:
                vis.add((i,j))
                s.append((i,j))
            if self.isinrectangle(i+1,j+1,A,B) and Valid[i+1][j+1] and (i+1,j+1) not in vis:
                s.append((i+1,j+1))
                if self.checkAB(i+1,j+1,A,B):
                    return "YES"
            if self.isinrectangle(i+1,j,A,B) and Valid[i+1][j] and (i+1,j) not in vis:
                s.append((i+1,j))
                if self.checkAB(i+1,j,A,B):
                    return "YES"
            if self.isinrectangle(i+1,j-1,A,B) and Valid[i+1][j-1] and (i+1,j-1) not in vis:
                s.append((i+1,j-1))
                if self.checkAB(i+1,j-1,A,B):
                    return "YES"
            if self.isinrectangle(i-1,j,A,B) and Valid[i-1][j] and (i-1,j) not in vis:
                s.append((i-1,j))
                if self.checkAB(i-1,j,A,B):
                    return "YES"
            if self.isinrectangle(i-1,j-1,A,B) and Valid[i-1][j-1] and (i-1,j-1) not in vis:
                s.append((i-1,j-1))
                if self.checkAB(i-1,j-1,A,B):
                    return "YES"
            if self.isinrectangle(i,j-1,A,B) and Valid[i][j-1] and (i,j-1) not in vis:
                s.append((i,j-1))
                if self.checkAB(i,j-1,A,B):
                    return "YES"
            if self.isinrectangle(i-1,j+1,A,B) and Valid[i-1][j+1] and (i-1,j+1) not in vis:
                s.append((i-1,j+1))
                if self.checkAB(i-1,j+1,A,B):
                    return "YES"
           if self.isinrectangle(i,j+1,A,B) and Valid[i][j+1] and (i,j+1) not in vis:
                s.append((i,j+1))
                if self.checkAB(i,j+1,A,B):
                    return "YES"
            i=s[-1][0]
            j=s[-1][1]
            s.pop()
        return "NO"