当前位置：首页 > news >正文

ZOJ Problem Set - 1002 Fire Net (Python)

news 来源：原创 2024/5/4 21:37:46

闲的无聊啊，重拾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的特殊语法都是现查现用的，不用说，很不优美，日后一定会有改进的~

转载于:https://www.cnblogs.com/vistach/archive/2011/09/22/2185124.html