Abstract: hunt the best point which get the most enemies in the map
The result:
(1, 1) (1, 2) [(1, 2)]
(1, 1) (2, 1) [(1, 2), (2, 1)]
(1, 2) (1, 3) [(2, 1), (1, 3)]
(2, 1) (3, 1) [(1, 3), (3, 1)]
(1, 3) (2, 3) [(3, 1), (2, 3)]
(3, 1) (3, 2) [(2, 3), (3, 2)]
(2, 3) (3, 3) [(3, 2), (3, 3)]
(3, 3) (3, 4) [(3, 4)]
(3, 3) (4, 3) [(3, 4), (4, 3)]
(3, 4) (3, 5) [(4, 3), (3, 5)]
(3, 5) (3, 6) [(3, 6)]
(3, 5) (2, 5) [(3, 6), (2, 5)]
(3, 5) (4, 5) [(3, 6), (2, 5), (4, 5)]
(3, 6) (3, 7) [(2, 5), (4, 5), (3, 7)]
(2, 5) (1, 5) [(4, 5), (3, 7), (1, 5)]
(4, 5) (5, 5) [(3, 7), (1, 5), (5, 5)]
(3, 7) (2, 7) [(1, 5), (5, 5), (2, 7)]
(3, 7) (4, 7) [(1, 5), (5, 5), (2, 7), (4, 7)]
(1, 5) (1, 6) [(5, 5), (2, 7), (4, 7), (1, 6)]
(5, 5) (5, 6) [(2, 7), (4, 7), (1, 6), (5, 6)]
(5, 5) (5, 4) [(2, 7), (4, 7), (1, 6), (5, 6), (5, 4)]
(2, 7) (1, 7) [(4, 7), (1, 6), (5, 6), (5, 4), (1, 7)]
(1, 7) (1, 8) [(1, 8)]
The ways: [(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4), (3, 5), (4, 5), (5, 5)]
The steps: 8
The enemies: 11
ok
The script:
# -*- coding: utf-8 -*-
"""
Created on Tue Jul 21 10:21:31 2015
@author: yuan
"""
import numpy as np
#the most enemies from (x,y) to (m,n) on a map
#record a queue using circling list
class queue:
def __init__(self,arr, q_len=1):
self.size=len(arr)
if q_len==1 or q_len<self.size:
self.q=[None]*self.size
self.q_len=self.size
else:
self.q=[None]*q_len
self.q_len=q_len
self.q[0]=0
self.q[1:self.size]=arr
self.head=1 #skip the index 0
self.tail=len(arr)+1 #the index of next element of arr
print 'Initiate queue:', self.q
def q_size(self):
#print 'Size of the queue:', self.size
return self.size
def export_arr(self):
if self.tail>self.head:
arr=self.q[self.head:self.tail]
elif self.tail==self.head:
arr=[]
else:
arr=self.q[self.head:(self.q_len+1)] + self.q[1:self.tail]
return arr
def enqueue(self, value):
if self.size<self.q_len:
#increase size
self.size +=1
#increase tail
if self.tail==(self.q_len+1):
self.tail=1
#add value
self.q[self.tail]=value
self.tail += 1
else:
print "queue is full, fail to adding", value
#print '##', self.q, self.head,self.tail
#return self.export_arr()
def dequeue(self):
#increase head
value='NA'
#print self.head, self.tail
if self.size>0:
value=self.q[self.head]
if self.head==self.q_len:
self.head=1
else:
self.head +=1
#decrease size
self.size -= 1
#print 'remove', value, self.export_arr()
return value
##################
class breadth_first_search(queue):
def __init__(self, pool,start):
self.pool=np.array(pool)
self.nrow=len(pool)
self.ncol=len(pool[1])
self.start=start
self.next=[[0,1],[0,-1],[-1,0],[1,0]]
self.book=list(self.pool)#book those visited points
self.enemies=np.zeros((self.nrow, self.ncol))
self.most_enemy=[]
#print self.pool, len(self.pool[1])
def export_ways(self):
point=self.most_enemy[0]
#
ways=[point]
while point!=self.start:
x=point[0]
y=point[1]
point=self.book[x][y]#father point
ways.insert(0, point)
steps=len(ways)-1
print 'The ways:', ways
print 'The steps:', steps
print 'The enemies:', self.most_enemy[1]
return ways
def count_enemies(self, point):
enemies=0
x=point[0]
y=point[1]
#count toward down
xy=range(y, self.nrow)
xy.reverse()
for i in xy:
if self.pool[i][y]==3:
break
elif self.pool[i][y]==1:
enemies += 1
#count toward up
for i in range(y):
if self.pool[i][y]==3:
break
elif self.pool[i][y]==1:
enemies += 1
#count toward left
xy=range(x)
xy.reverse()
for i in xy:
if self.pool[x][i]==3:
break
elif self.pool[x][i]==1:
enemies += 1
#count toward right
for i in range(x, self.ncol):
#print y,i
if self.pool[x][i]==3:
break
elif self.pool[x][i]==1:
enemies += 1
return enemies
def search_most(self):
q=queue([self.start], self.nrow*self.ncol)
self.book[self.start[0]][self.start[1]]=self.start #book start point
self.most_enemy=[self.start,self.count_enemies(self.start)]
while q.q_size()>0:
point=q.dequeue()
for i in range(4):
x=point[0]+self.next[i][0]
y=point[1]+self.next[i][1]
#print x,y
#judge if beyond bound
if x<1 or x>=self.nrow or y<1 or y>=self.ncol:
continue
#if obstacle or already passed
if self.pool[x][y]==0 and self.book[x][y]==0:
new_point=(x,y)
enemy_num=self.count_enemies(new_point)
q.enqueue(new_point)
self.book[x][y]=point #write its father node
print point, new_point, q.export_arr()
#
if self.most_enemy[1]<enemy_num:
self.most_enemy=[new_point,enemy_num]
ways=self.export_ways()
return ways
#main
if __name__ == "__main__":
#0 empty, 1 obstcle, None null
#1=enzemy, 3=wall, 0=empty
pool=[ [None,None,None,None,None,None,None,None,None,None,None,None,None,None],
[None,0,0,0,1,0,0,0,0,3,0,0,0,0],[None,0,3,0,3,0,3,0,3,3,3,0,3,0],
[None,0,0,0,0,0,0,0,3,3,1,0,0,1],[None,1,3,0,3,0,3,0,3,0,3,0,3,1],
[None,1,0,1,0,0,0,1,1,1,0,0,1,0],[None,0,3,0,3,1,3,0,3,0,3,1,3,0],
[None,1,0,1,1,1,0,1,3,0,1,0,1,0],[None,0,3,0,3,1,3,0,3,0,3,1,3,1],
[None,0,0,1,1,0,3,1,1,3,1,0,0,0],[None,1,3,0,3,1,3,1,3,0,3,1,3,1],
[None,0,0,0,1,1,0,0,0,1,0,0,3,0] ]
#coordinate of the start point
start=(1,1)
#coordinate of the end point
s=breadth_first_search(pool,start)
s.search_most()
print 'ok'
No comments:
Post a Comment