ZOJ Problem Set 1002 Fire Net (Python)

闲的无聊啊，重拾ACM啊…… 可是还用C/JAVA就没意思啦。最近对Python挺感兴趣，但是一直没有机会使用一下，终于找到个支持Python的Online Judge——Zhejiang University Online Judge（ZOJ）（http://acm.zju.edu.cn），好吧，开始。

P1002，变形的八皇后问题，果断深度搜索。

   1 import sys

  2 
  3 class point:
  4     x=0
  5     y=0
  6     def __init__(self,p,N):
  7         self.x=p/N
  8         self.y=p%N
  9 
 10 
 11 
 12 maxN=0
 13 
 14 def check(now,lst,p):
 15     global lstAll
 16     
 17     for t in lst:
 18         if p.x==t.x:
 19             res=False
 20             rangeX=range(0,1)
 21             if p.y<t.y:
 22                 rangeX=range(p.y,t.y)
 23             else:
 24                 rangeX=range(t.y,p.y)
 25             
 26             for py in rangeX:
 27                 if lstAll[p.x][py]=='X':
 28                     res=True
 29                     break
 30             if res==False:
 31                 return False
 32         elif p.y==t.y:
 33             res=False
 34             rangeX=range(0,1)
 35             if p.x<t.x:
 36                 rangeX= range(p.x,t.x)
 37             else:
 38                 rangeX=  range(t.x,p.x)
 39             for px in rangeX:
 40                 if lstAll[px][p.y]=='X':
 41                     res=True
 42                     break
 43             if res==False:
 44                 return False
 45         else:
 46             continue
 47     return True
 48 
 49 
 50 def dg(N,now,lst):
 51     global maxN
 52     global lstAll
 53     
 54     if now==0:
 55         p=getNextPoint(None)
 56         while p!=None:
 57             lst.append(p)
 58             dg(N,now+1,lst)
 59             lst.remove(p)
 60             p=getNextPoint(p)
 61     else:
 62         p=getNextPoint(lst[now-1])
 63         while p!=None:
 64             if check(now, lst,p):
 65                 lst.append(p)
 66                 dg(N,now+1,lst)
 67                 lst.remove(p)
 68             p=getNextPoint(p)
 69         if maxN<now:
 70             maxN=now
 71     
 72 
 73 def getNextPoint(nowPoint):
 74     global N
 75     global lstAll
 76     if nowPoint==None:
 77         p=-1
 78     else:
 79         p=nowPoint.x*N+nowPoint.y
 80     while True:
 81         p=p+1
 82         np=point(p=p,N=N)
 83         if np.y==N:
 84             np.x=np.x+1
 85         if np.x==N:
 86             return None
 87         if lstAll[np.x][np.y]!='X':
 88             return np
 89 
 90 
 91 
 92 #fileHandle = open ('g:/input.txt') 
 93 #N=int(fileHandle.readline())
 94 N=int(raw_input())
 95 while N!=0:
 96     lstAll=[]
 97     for i in range(0,N):
 98         #strTemp=fileHandle.readline()
 99         strTemp=raw_input()
100         lstT=[]
101         for j in range(0,N):
102             lstT.append(strTemp[j])
103         lstAll.append(lstT)
104     
105     dg(N,0,[])
106     print maxN;
107     maxN=0
108     #N=int(fileHandle.readline())
109     N=int(raw_input())
110 #fileHandle.close()

第一次用Python写这么长的程序啊，很多Python的特殊语法都是现查现用的，不用说，很不优美，日后一定会有改进的~