Fire Net

ZOJ Problem Set - 1002

def Input(L,n):
        if type(L)==list:
                for i in range(0,n):
                        L.append([t for t in sys.stdin.readline().rstrip('\n')])
def place_bh(L,row,col,n):
        if L[row][col]=='X':
                return False
        j=n-1
        while(j>=0):
                if j==col:
                        j-=1
                        continue
                if L[row][j]=='X':
                        break
                if L[row][j]=='O':
                        return False
                j-=1

        k=n-1
        while(k>=0):
                if k==row:
                        k-=1
                        continue
                if L[k][col]=='X':
                        break
                if L[k][col]=='O':
                        return False
                k-=1

        return True

def FindMax(L,k,n):
        curnum=0
        j=k
        while j<k+n*n:
                if j>=n*n:
                        z=j-n*n
                else:
                        z=j

                row=z/n
                col=z%n
                if place_bh(L,row,col,n):
                        L[row][col]='O'
                        curnum+=1

                j+=1

        return curnum

def main():
        while True:
                n=int(sys.stdin.readline().rstrip('\n'))
                if n==0:
                        break

                L=[]
                maxn=0
                Input(L,n)
                for k in range(0,n*n):
                        t=copy.deepcopy(L)
                        curn=FindMax(t,k,n)
                        if maxn<curn:
                                maxn=curn

                print maxn

if __name__=='__main__':
        import copy
        import sys
        main()

突然发现我没有用回溯法哎。

Python做算法可以偷懒。呵呵

参考:链接

Comments