1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| N = 6
D = 8
offsetX = [-1,1,-1,1,-2,-2,2,2]
offsetY = [-2,-2,2,2,-1,1,-1,1]
chessBoard= [[0]*N for i in xrange(N)]
class ChessNode:
def __init__(self, x, y):
self.x, self.y = x, y
self.wayout = 0
def isCorrect(self, count=0):
return self.x<N and self.x>=0 and self.y<N and self.y>=0 and (chessBoard[self.x][self.y]==0 or chessBoard[self.x][self.y]==1 and count==N*N+1)
def setWayout(self, count=0):
for direction in xrange(D):
nx, ny = self.x + offsetX[direction], self.y + offsetY[direction]
aNode = ChessNode(nx, ny)
self.wayout += 1 if aNode.isCorrect(count=count) else 0
def show(self):
print '(%s,%s)=> %s wayouts' % (self.x, self.y, self.wayout)
class HorseJump:
def success(self):
for i in xrange(N):
for j in xrange(N):
print "%2d " % chessBoard[i][j],
print
print '====================='
def greedyDFS(self, node, count):
if self.found: return
if count > N*N:
self.success()
return
v = []
for direction in xrange(D):
newNode = ChessNode(node.x+offsetX[direction], node.y+offsetY[direction])
if newNode.isCorrect(count=count+1):
newNode.setWayout(count=count+1)
v.append(newNode)
sv = sorted(v, lambda x,y: x.wayout < y.wayout)
for it in sv:
chessBoard[it.x][it.y] = count
self.greedyDFS(it, count+1)
chessBoard[node.x][node.y] = 0
def greedyWalk(self, ox, oy):
self.ox, self.oy = ox, oy
node = ChessNode(ox, oy)
if not node.isCorrect():
print "illegal init x,y"
return
self.success()
chessBoard[ox][oy]=1
self.found = False
self.greedyDFS(node, count=2)
h=HorseJump()
h.greedyWalk(4,3)
|