Python: Depth-First search (5)

Abstract: the best point for putting a bomb










To kill the most enemies, the bomb should be put the point (4,4), where a total of 11 can be killed.

The script:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun  7 18:44:43 2015

@author: yuan
"""

import numpy as np
#the shortest way from (x,y) to (m,n) on a map


#depth first search
class depth_first:
   
    def __init__(self, map, start):
        self.pool=map
        self.nrow=len(map)
        self.ncol=len(map[0])
        print self.nrow, self.ncol
        self.steps=map
        self.start=start
        self.out={'enemy':0, 'x':0, 'y':0}# store all steps from (x,y) to (m,n)
        self.next=[[0,1], [1,0], [0,-1],[-1,0]]
   
    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 DFS(self, point, ways):
        enemy_num=self.count_enemies(point)
        print enemy_num, '=', point
        #judge if reach the end point
        if self.out['enemy'] < enemy_num:
            self.out['enemy']=enemy_num
            self.out['x']=point[0]
            self.out['y']=point[1]
            print self.out
       
        #print 'step:', step
        for i in range(4):
            tx=point[0]+self.next[i][0]
            ty=point[1]+self.next[i][1]           
            #print tx,ty
            if (0<=tx<=self.ncol and 1<=ty<=self.nrow):
                if(self.pool[tx][ty]==0 and ways[tx][ty]==0 ):
                    ways[tx][ty]=2
                    new_start=[tx,ty]
                    print new_start
                    self.DFS(new_start, ways)
                    ways[tx][ty]=0
        return
           
    def shortest_way(self):
        ways=list(self.pool)
        #search
        self.DFS(self.start, ways)
        print 'The most enemies:', self.out

        return self.out
   

#main programming
#read the map
#1=enzemy, 3=wall, 0=empty
map=[ [0,0,0,1,0,0,0,0,3,0,0,0,0],[0,3,0,3,0,3,0,3,3,3,0,3,0],
      [0,0,0,0,0,0,0,3,3,1,0,0,1],[1,3,0,3,0,3,0,3,0,3,0,3,1],
      [1,0,1,0,0,0,1,1,1,0,0,1,0],[0,3,0,3,1,3,0,3,0,3,1,3,0],
      [1,0,1,1,1,0,1,3,0,1,0,1,0],[0,3,0,3,1,3,0,3,0,3,1,3,1],
      [0,0,1,1,0,3,1,1,3,1,0,0,0],[1,3,0,3,1,3,1,3,0,3,1,3,1],
      [0,0,0,1,1,0,0,0,1,0,0,3,0] ]


#coordinate of the start point
start=[0,0]

#coordinate of the end point
s=depth_first(map, start)
out=s.shortest_way()