Created
September 4, 2015 16:47
-
-
Save SaptakS/99cd0ca65ac78ba9b7c3 to your computer and use it in GitHub Desktop.
Maze Problem (A.I.)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
from math import sqrt | |
import heapq | |
import itertools | |
class Node: | |
def __init__(self, x, y, cost): | |
self.x = x | |
self.y = y | |
self.cost = cost | |
def __eq__(self, other): | |
return (self.x, self.y) == (other.x, other.y) | |
class Environment: | |
def __init__(self, grid, m, n): | |
self.grid = grid | |
self.m = m | |
self.n = n | |
def navigable(self, i, j): | |
if self.grid[i][j] == 0: | |
return True | |
else: | |
return False | |
def get_cost(self, src, dest): | |
(src_i, src_j) = src | |
(dest_i, dest_j) = dest | |
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
class Agent: | |
def __init__(self, query, env): | |
(self.src_i, self.src_j) = query[0] | |
(self.dest_i, self.dest_j) = query[1] | |
self.env = env | |
def next_fringes(self, present): | |
(i, j) = (present.x, present.y) | |
cost = present.cost | |
newf = [] | |
counter = itertools.count() | |
#right move | |
if j + 1 < self.env.n and self.env.navigable(i, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j+1)) | |
entry = [next_cost, count, Node(i, j+1, next_cost)] | |
heapq.heappush(newf, entry) | |
#down-right move | |
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1)) | |
entry = [next_cost, count, Node(i + 1, j+1, next_cost)] | |
heapq.heappush(newf, entry) | |
#down move | |
if i + 1 < self.env.m and self.env.navigable(i + 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j)) | |
entry = [next_cost, count, Node(i+1, j, next_cost)] | |
heapq.heappush(newf, entry) | |
#down-left move | |
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1)) | |
entry = [next_cost, count, Node(i+1, j-1, next_cost)] | |
heapq.heappush(newf, entry) | |
#left move | |
if j - 1 >= 0 and self.env.navigable(i, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j-1)) | |
entry = [next_cost, count, Node(i, j-1, next_cost)] | |
heapq.heappush(newf, entry) | |
#up-left move | |
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1)) | |
entry = [next_cost, count, Node(i-1, j-1, next_cost)] | |
heapq.heappush(newf, entry) | |
#up move | |
if i - 1 >= 0 and self.env.navigable(i - 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j)) | |
entry = [next_cost, count, Node(i-1, j, next_cost)] | |
heapq.heappush(newf, entry) | |
#up-right move | |
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1)) | |
entry = [next_cost, count, Node(i-1, j+1, next_cost)] | |
heapq.heappush(newf, entry) | |
'''for f in nextf: | |
print f.x, f.y, f.cost''' | |
#nextf.sort(key=lambda x: x.cost) | |
return newf | |
def solver(self): | |
start = Node(self.src_i, self.src_j, 0) | |
fringe = [start] | |
visited = [] | |
while fringe: | |
next_fringe = fringe.pop(0) | |
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j): | |
#print "found" | |
return next_fringe.cost | |
#for kk in visited: | |
#print "VIS" , kk.x, kk.y, kk.cost | |
#for kk in fringe: | |
#print "fr" , kk.x, kk.y, kk.cost | |
nextFringes = self.next_fringes(next_fringe) | |
#nextFringes.sort(key = lambda x: x.cost) | |
for newf in nextFringes: | |
if newf[2] not in visited and newf[2] not in fringe: | |
fringe.append(newf[2]) | |
#print newf[1].x, newf[1].y, newf[1].cost | |
'''else: | |
print newf[1].x, newf[1].y, newf[1].cost, "Already"''' | |
visited.append(next_fringe) | |
fringe.sort(key=lambda i: i.cost) | |
'''for kkk in fringe: | |
print (kkk.x, kkk.y, kkk.cost)''' | |
##input | |
k = raw_input().split() | |
m = int(k[0]) | |
n = int(k[1]) | |
grid = [] | |
for i in range(m): | |
row = [] | |
row = [int(x) for x in raw_input().split()] | |
grid.append(row) | |
#print grid | |
x = int(raw_input()) | |
query = [] | |
for i in range(x): | |
k = raw_input().split() | |
query.append([(int(k[0]), int(k[1])),(int(k[2]), int(k[3]))]) | |
e = Environment(grid, m, n) | |
for i in range(x): | |
a = Agent(query[i], e) | |
cost = a.solver() | |
print int(round(cost)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
""" | |
Created on Thu Sep 03 10:16:00 2015 | |
@author: SAPTAK | |
""" | |
from math import sqrt | |
import heapq | |
import itertools | |
class Node: | |
def __init__(self, x, y, cost, total=0): | |
self.x = x | |
self.y = y | |
self.cost = cost | |
self.total = total | |
def __eq__(self, other): | |
return (self.x, self.y) == (other.x, other.y) | |
class Environment: | |
def __init__(self, grid, m, n): | |
self.grid = grid | |
self.m = m | |
self.n = n | |
def navigable(self, i, j): | |
if self.grid[i][j] == 0: | |
return True | |
else: | |
return False | |
def get_cost(self, src, dest): | |
(src_i, src_j) = src | |
(dest_i, dest_j) = dest | |
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
class Agent: | |
def __init__(self, query, env): | |
(self.src_i, self.src_j) = query[0] | |
(self.dest_i, self.dest_j) = query[1] | |
self.env = env | |
def heuristic(self, (x, y)): | |
(i, j) = (x, y) | |
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2)) | |
def next_fringes(self, present): | |
(i, j) = (present.x, present.y) | |
cost = present.cost | |
newf = [] | |
counter = itertools.count() | |
#right move | |
if j + 1 < self.env.n and self.env.navigable(i, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-right move | |
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i + 1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down move | |
if i + 1 < self.env.m and self.env.navigable(i + 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-left move | |
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#left move | |
if j - 1 >= 0 and self.env.navigable(i, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-left move | |
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up move | |
if i - 1 >= 0 and self.env.navigable(i - 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-right move | |
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
'''for f in nextf: | |
print f.x, f.y, f.cost''' | |
#nextf.sort(key=lambda x: x.cost) | |
return newf | |
def solver(self): | |
start = Node(self.src_i, self.src_j, 0) | |
fringe = [start] | |
visited = [] | |
while fringe: | |
next_fringe = fringe.pop(0) | |
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j): | |
#print "found" | |
return next_fringe.cost | |
#for kk in visited: | |
#print "VIS" , kk.x, kk.y, kk.cost | |
#for kk in fringe: | |
#print "fr" , kk.x, kk.y, kk.cost | |
nextFringes = self.next_fringes(next_fringe) | |
#nextFringes.sort(key = lambda x: x.cost) | |
for newf in nextFringes: | |
if newf[2] not in visited and newf[2] not in fringe: | |
fringe.append(newf[2]) | |
#print newf[1].x, newf[1].y, newf[1].cost | |
'''else: | |
print newf[1].x, newf[1].y, newf[1].cost, "Already"''' | |
visited.append(next_fringe) | |
fringe.sort(key=lambda i: i.total) | |
'''for kkk in fringe: | |
print (kkk.x, kkk.y, kkk.cost, kkk.total)''' | |
##input | |
k = raw_input().split() | |
m = int(k[0]) | |
n = int(k[1]) | |
grid = [] | |
for i in range(m): | |
row = [] | |
row = [int(x) for x in raw_input().split()] | |
grid.append(row) | |
#print grid | |
x = int(raw_input()) | |
query = [] | |
for i in range(x): | |
k = raw_input().split() | |
query.append([(int(k[0]), int(k[1])),(int(k[2]), int(k[3]))]) | |
e = Environment(grid, m, n) | |
for i in range(x): | |
a = Agent(query[i], e) | |
cost = a.solver() | |
print int(round(cost)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
""" | |
Created on Thu Sep 03 10:42:50 2015 | |
@author: SAPTAK | |
""" | |
from math import sqrt | |
import heapq | |
import itertools | |
class Pque: | |
def __init__(self): | |
self.queue = [] | |
self.index = 0 | |
def push(self, item): | |
heapq.heappush(self.queue, (item.total, item)) | |
self.index += 1 | |
def pop(self): | |
return heapq.heappop(self.queue)[-1] | |
class Node: | |
def __init__(self, x, y, cost, total=0): | |
self.x = x | |
self.y = y | |
self.cost = cost | |
self.total = total | |
def __eq__(self, other): | |
return (self.x, self.y) == (other.x, other.y) | |
class Environment: | |
def __init__(self, grid, m, n): | |
self.grid = grid | |
self.m = m | |
self.n = n | |
def navigable(self, now, nex): | |
(now_i,now_j) = now | |
(nex_i, nex_j) = nex | |
#check for diagonal | |
if(self.get_cost(now, nex) > 1.0): | |
#down-right | |
if nex_i == now_i + 1 and nex_j == now_j + 1 : | |
if self.grid[nex_i][nex_j] == 0 and self.grid[nex_i-1][nex_j] == 0 and self.grid[nex_i][nex_j-1] == 0: | |
return True | |
else: | |
return False | |
#down-left | |
if nex_i == now_i + 1 and nex_j == now_j - 1: | |
if self.grid[nex_i][nex_j] == 0 and self.grid[nex_i-1][nex_j] == 0 and self.grid[nex_i][nex_j+1] == 0: | |
return True | |
else: | |
return False | |
#up-right | |
if nex_i == now_i - 1 and nex_j == now_j + 1: | |
if self.grid[nex_i][nex_j] == 0 and self.grid[nex_i+1][nex_j] == 0 and self.grid[nex_i][nex_j-1] == 0: | |
#print "here", nex_i,nex_j | |
return True | |
else: | |
return False | |
#up-left | |
if nex_i == now_i -1 and nex_j == now_j - 1: | |
if self.grid[nex_i][nex_j] == 0 and self.grid[nex_i+1][nex_j] == 0 and self.grid[nex_i][nex_j+1] == 0: | |
return True | |
else: | |
return False | |
else: | |
if self.grid[nex_i][nex_j] == 0: | |
return True | |
else: | |
return False | |
def get_cost(self, src, dest): | |
(src_i, src_j) = src | |
(dest_i, dest_j) = dest | |
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
class Agent: | |
def __init__(self, query, env): | |
(self.src_i, self.src_j) = query[0] | |
(self.dest_i, self.dest_j) = query[1] | |
self.env = env | |
def heuristic(self, (x, y)): | |
(i, j) = (x, y) | |
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2)) | |
def next_fringes(self, present): | |
(i, j) = (present.x, present.y) | |
cost = present.cost | |
newf = [] | |
counter = itertools.count() | |
#right move | |
if j + 1 < self.env.n and self.env.navigable((i,j),(i, j + 1)): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-right move | |
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable((i,j),(i + 1, j + 1)): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i + 1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down move | |
if i + 1 < self.env.m and self.env.navigable((i,j),(i + 1, j)): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-left move | |
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable((i,j),(i + 1, j - 1)): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#left move | |
if j - 1 >= 0 and self.env.navigable((i,j),(i, j - 1)): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-left move | |
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable((i,j),(i - 1, j - 1)): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up move | |
if i - 1 >= 0 and self.env.navigable((i,j),(i - 1, j)): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-right move | |
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable((i,j),(i-1, j + 1)): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
'''for f in nextf: | |
print f.x, f.y, f.cost''' | |
#nextf.sort(key=lambda x: x.cost) | |
return newf | |
def solver(self): | |
start = Node(self.src_i, self.src_j, 0) | |
fringe = Pque() | |
fringe.push(start) | |
visited = [] | |
while fringe.queue != []: | |
next_fringe = fringe.pop() | |
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j): | |
#print "found" | |
return next_fringe.cost | |
#for kk in visited: | |
#print "VIS" , kk.x, kk.y, kk.cost | |
#for kk in fringe: | |
#print "fr" , kk.x, kk.y, kk.cost | |
nextFringes = self.next_fringes(next_fringe) | |
#nextFringes.sort(key = lambda x: x.cost) | |
for newf in nextFringes: | |
if newf[2] not in visited:# and newf[2] not in [x[1] for x in fringe.queue]: | |
fl = 0 | |
for x in fringe.queue: | |
if x[1] == newf[2]: | |
fl = 1 | |
break | |
if fl == 0: | |
fringe.push(newf[2]) | |
#print newf[1].x, newf[1].y, newf[1].cost | |
'''else: | |
print newf[1].x, newf[1].y, newf[1].cost, "Already"''' | |
visited.append(next_fringe) | |
#heapq.heapify(fringe) | |
#fringe.sort(key=lambda i: i.total) | |
'''print "Fr" | |
for kkk in fringe.queue: | |
print (kkk[1].x, kkk[1].y, kkk[1].cost, kkk[1].total)''' | |
##input | |
k = raw_input().split() | |
m = int(k[0]) | |
n = int(k[1]) | |
grid = [] | |
for i in range(m): | |
row = [] | |
row = [int(x) for x in raw_input().split()] | |
grid.append(row) | |
#print grid | |
x = int(raw_input()) | |
query = [] | |
for i in range(x): | |
k = raw_input().split() | |
query.append([(int(k[0]), int(k[1])),(int(k[2]), int(k[3]))]) | |
e = Environment(grid, m, n) | |
for i in range(x): | |
a = Agent(query[i], e) | |
cost = a.solver() | |
print int(round(cost)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
""" | |
Created on Thu Sep 03 10:16:00 2015 | |
@author: SAPTAK | |
""" | |
from math import sqrt | |
import heapq | |
import itertools | |
class Node: | |
def __init__(self, x, y, cost, total=0): | |
self.x = x | |
self.y = y | |
self.cost = cost | |
self.total = total | |
def __eq__(self, other): | |
return (self.x, self.y) == (other.x, other.y) | |
class Environment: | |
def __init__(self, grid, m, n): | |
self.grid = grid | |
self.m = m | |
self.n = n | |
def navigable(self, i, j): | |
if self.grid[i][j] == 0: | |
return True | |
else: | |
return False | |
def get_cost(self, src, dest): | |
(src_i, src_j) = src | |
(dest_i, dest_j) = dest | |
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
class Agent: | |
def __init__(self, query, env): | |
(self.src_i, self.src_j) = query[0] | |
(self.dest_i, self.dest_j) = query[1] | |
self.env = env | |
def heuristic(self, (x, y)): | |
(i, j) = (x, y) | |
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2)) | |
def next_fringes(self, present): | |
(i, j) = (present.x, present.y) | |
cost = present.cost | |
newf = [] | |
counter = itertools.count() | |
#right move | |
if j + 1 < self.env.n and self.env.navigable(i, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-right move | |
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i + 1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down move | |
if i + 1 < self.env.m and self.env.navigable(i + 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-left move | |
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#left move | |
if j - 1 >= 0 and self.env.navigable(i, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-left move | |
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up move | |
if i - 1 >= 0 and self.env.navigable(i - 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-right move | |
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
'''for f in nextf: | |
print f.x, f.y, f.cost''' | |
#nextf.sort(key=lambda x: x.cost) | |
return newf | |
def solver(self): | |
start = Node(self.src_i, self.src_j, 0) | |
fringe = [start] | |
visited = [] | |
while fringe: | |
next_fringe = fringe.pop(0) | |
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j): | |
#print "found" | |
return next_fringe.cost | |
#for kk in visited: | |
#print "VIS" , kk.x, kk.y, kk.cost | |
#for kk in fringe: | |
#print "fr" , kk.x, kk.y, kk.cost | |
nextFringes = self.next_fringes(next_fringe) | |
#nextFringes.sort(key = lambda x: x.cost) | |
for newf in nextFringes: | |
if newf[2] not in visited and newf[2] not in fringe: | |
fringe.append(newf[2]) | |
#print newf[1].x, newf[1].y, newf[1].cost | |
'''else: | |
print newf[1].x, newf[1].y, newf[1].cost, "Already"''' | |
visited.append(next_fringe) | |
fringe.sort(key=lambda i: i.total) | |
'''for kkk in fringe: | |
print (kkk.x, kkk.y, kkk.cost, kkk.total)''' | |
##input | |
k = raw_input().split() | |
m = int(k[0]) | |
n = int(k[1]) | |
grid = [] | |
for i in range(m): | |
row = [] | |
row = [int(x) for x in raw_input().split()] | |
grid.append(row) | |
#print grid | |
x = int(raw_input()) | |
query = [] | |
for i in range(x): | |
k = raw_input().split() | |
query.append((int(k[0]), int(k[1]))) | |
'''print query[0] | |
q = [query[0], (0,0)] | |
print q | |
''' | |
e = Environment(grid, m, n) | |
for i in range(x): | |
cost = 0 | |
q1 = [query[i], (0,0)] | |
q2 = [(0,0), (0,n-1)] | |
q3 = [(0,n-1), (m-1,n-1)] | |
q4 = [(m-1,n-1), (m-1,0)] | |
a = Agent(q1, e) | |
cost += a.solver() | |
a = Agent(q2, e) | |
cost += a.solver() | |
a = Agent(q3, e) | |
cost += a.solver() | |
a = Agent(q4, e) | |
cost += a.solver() | |
print int(round(cost)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
""" | |
Created on Thu Sep 03 12:19:19 2015 | |
@author: SAPTAK | |
""" | |
from math import sqrt | |
import heapq | |
import itertools | |
class Node: | |
def __init__(self, x, y, cost, total=0): | |
self.x = x | |
self.y = y | |
self.cost = cost | |
self.total = total | |
def __eq__(self, other): | |
return (self.x, self.y) == (other.x, other.y) | |
class Environment: | |
def __init__(self, grid, m, n): | |
self.grid = grid | |
self.m = m | |
self.n = n | |
def navigable(self, i, j): | |
if self.grid[i][j] == 0: | |
return True | |
else: | |
return False | |
def get_cost(self, src, dest): | |
(src_i, src_j) = src | |
(dest_i, dest_j) = dest | |
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
class Agent: | |
def __init__(self, query, env): | |
(self.src_i, self.src_j) = query[0] | |
(self.dest_i, self.dest_j) = query[1] | |
self.env = env | |
def heuristic(self, (x, y)): | |
(i, j) = (x, y) | |
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2)) | |
def next_fringes(self, present): | |
(i, j) = (present.x, present.y) | |
cost = present.cost | |
newf = [] | |
counter = itertools.count() | |
#right move | |
if j + 1 < self.env.n and self.env.navigable(i, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-right move | |
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i + 1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down move | |
if i + 1 < self.env.m and self.env.navigable(i + 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-left move | |
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#left move | |
if j - 1 >= 0 and self.env.navigable(i, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-left move | |
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up move | |
if i - 1 >= 0 and self.env.navigable(i - 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-right move | |
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
'''for f in nextf: | |
print f.x, f.y, f.cost''' | |
#nextf.sort(key=lambda x: x.cost) | |
return newf | |
def solver(self): | |
start = Node(self.src_i, self.src_j, 0) | |
fringe = [start] | |
visited = [] | |
while fringe: | |
next_fringe = fringe.pop(0) | |
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j): | |
#print "found" | |
return next_fringe.cost | |
#for kk in visited: | |
#print "VIS" , kk.x, kk.y, kk.cost | |
#for kk in fringe: | |
#print "fr" , kk.x, kk.y, kk.cost | |
nextFringes = self.next_fringes(next_fringe) | |
#nextFringes.sort(key = lambda x: x.cost) | |
for newf in nextFringes: | |
if newf[2] not in visited and newf[2] not in fringe: | |
fringe.append(newf[2]) | |
#print newf[1].x, newf[1].y, newf[1].cost | |
'''else: | |
print newf[1].x, newf[1].y, newf[1].cost, "Already"''' | |
visited.append(next_fringe) | |
fringe.sort(key=lambda i: i.total) | |
'''for kkk in fringe: | |
print (kkk.x, kkk.y, kkk.cost, kkk.total)''' | |
##input | |
k = raw_input().split() | |
m = int(k[0]) | |
n = int(k[1]) | |
grid = [] | |
for i in range(m): | |
row = [] | |
row = [int(x) for x in raw_input().split()] | |
grid.append(row) | |
#print grid | |
x = int(raw_input()) | |
query = [] | |
for i in range(x): | |
k = raw_input().split() | |
query.append((int(k[0]), int(k[1]))) | |
'''print query[0] | |
q = [query[0], (0,0)] | |
print q | |
''' | |
e = Environment(grid, m, n) | |
for i in range(x): | |
minimum = 1000000 | |
q1 = [query[i], (0,0)] | |
q2 = [query[i], (0,n-1)] | |
q3 = [query[i], (m-1,n-1)] | |
q4 = [query[i], (m-1,0)] | |
a = Agent(q1, e) | |
cost = a.solver() | |
if cost < minimum: | |
minimum = cost | |
a = Agent(q2, e) | |
cost = a.solver() | |
if cost < minimum: | |
minimum = cost | |
a = Agent(q3, e) | |
cost = a.solver() | |
if cost < minimum: | |
minimum = cost | |
a = Agent(q4, e) | |
cost = a.solver() | |
if cost < minimum: | |
minimum = cost | |
print int(round(minimum)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
""" | |
Created on Thu Sep 03 12:20:24 2015 | |
@author: SAPTAK | |
""" | |
from math import sqrt | |
import heapq | |
import itertools | |
from itertools import permutations | |
class Node: | |
def __init__(self, x, y, cost, total=0): | |
self.x = x | |
self.y = y | |
self.cost = cost | |
self.total = total | |
def __eq__(self, other): | |
return (self.x, self.y) == (other.x, other.y) | |
class Environment: | |
def __init__(self, grid, m, n): | |
self.grid = grid | |
self.m = m | |
self.n = n | |
def navigable(self, i, j): | |
if self.grid[i][j] == 0: | |
return True | |
else: | |
return False | |
def get_cost(self, src, dest): | |
(src_i, src_j) = src | |
(dest_i, dest_j) = dest | |
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
class Agent: | |
def __init__(self, query, env): | |
(self.src_i, self.src_j) = query[0] | |
(self.dest_i, self.dest_j) = query[1] | |
self.env = env | |
def heuristic(self, (x, y)): | |
(i, j) = (x, y) | |
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2)) | |
def next_fringes(self, present): | |
(i, j) = (present.x, present.y) | |
cost = present.cost | |
newf = [] | |
counter = itertools.count() | |
#right move | |
if j + 1 < self.env.n and self.env.navigable(i, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-right move | |
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i + 1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down move | |
if i + 1 < self.env.m and self.env.navigable(i + 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-left move | |
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#left move | |
if j - 1 >= 0 and self.env.navigable(i, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-left move | |
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up move | |
if i - 1 >= 0 and self.env.navigable(i - 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-right move | |
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
'''for f in nextf: | |
print f.x, f.y, f.cost''' | |
#nextf.sort(key=lambda x: x.cost) | |
return newf | |
def solver(self): | |
start = Node(self.src_i, self.src_j, 0) | |
fringe = [start] | |
visited = [] | |
while fringe: | |
next_fringe = fringe.pop(0) | |
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j): | |
#print "found" | |
return next_fringe.cost | |
#for kk in visited: | |
#print "VIS" , kk.x, kk.y, kk.cost | |
#for kk in fringe: | |
#print "fr" , kk.x, kk.y, kk.cost | |
nextFringes = self.next_fringes(next_fringe) | |
#nextFringes.sort(key = lambda x: x.cost) | |
for newf in nextFringes: | |
if newf[2] not in visited and newf[2] not in fringe: | |
fringe.append(newf[2]) | |
#print newf[1].x, newf[1].y, newf[1].cost | |
'''else: | |
print newf[1].x, newf[1].y, newf[1].cost, "Already"''' | |
visited.append(next_fringe) | |
fringe.sort(key=lambda i: i.total) | |
'''for kkk in fringe: | |
print (kkk.x, kkk.y, kkk.cost, kkk.total)''' | |
##input | |
k = raw_input().split() | |
m = int(k[0]) | |
n = int(k[1]) | |
grid = [] | |
for i in range(m): | |
row = [] | |
row = [int(x) for x in raw_input().split()] | |
grid.append(row) | |
#print grid | |
e = Environment(grid, m, n) | |
x = int(raw_input()) | |
query = [] | |
for i in range(x): | |
k = raw_input().split() | |
query.append((int(k[0]), int(k[1]))) | |
'''print query[0] | |
q = [query[0], (0,0)] | |
print q | |
''' | |
destinations = {'TL': (0,0), | |
'TR': (0, n-1), | |
'DR': (m-1, n-1), | |
'DL': (m-1, 0)} | |
desti_tags = ['TL', 'TR', 'DR', 'DL'] | |
perm_list = list(permutations(desti_tags)) | |
#print perm_list | |
for i in range(x): | |
minimum = 100000 | |
for perm in perm_list: | |
cost = 0 | |
q1 = [query[i], destinations[perm[0]]] | |
q2 = [destinations[perm[0]], destinations[perm[1]]] | |
q3 = [destinations[perm[1]], destinations[perm[2]]] | |
q4 = [destinations[perm[2]], destinations[perm[3]]] | |
a = Agent(q1, e) | |
cost += a.solver() | |
a = Agent(q2, e) | |
cost += a.solver() | |
a = Agent(q3, e) | |
cost += a.solver() | |
a = Agent(q4, e) | |
cost += a.solver() | |
if cost < minimum: | |
minimum = cost | |
print int(round(minimum)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
""" | |
Created on Thu Sep 03 10:16:00 2015 | |
@author: SAPTAK | |
""" | |
from math import sqrt | |
import heapq | |
import itertools | |
class Node: | |
def __init__(self, x, y, cost, total=0): | |
self.x = x | |
self.y = y | |
self.cost = cost | |
self.total = total | |
def __eq__(self, other): | |
return (self.x, self.y) == (other.x, other.y) | |
class Environment: | |
def __init__(self, grid, m, n): | |
self.grid = grid | |
self.m = m | |
self.n = n | |
def navigable(self, i, j): | |
if self.grid[i][j] == 0: | |
return True | |
else: | |
return False | |
def get_cost(self, src, dest): | |
(src_i, src_j) = src | |
(dest_i, dest_j) = dest | |
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
class Agent: | |
def __init__(self, query, env): | |
(self.src_i, self.src_j) = query[0] | |
(self.dest_i, self.dest_j) = query[1] | |
self.env = env | |
def heuristic(self, (x, y)): | |
(i, j) = (x, y) | |
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2)) | |
def next_fringes(self, present): | |
(i, j) = (present.x, present.y) | |
cost = present.cost | |
newf = [] | |
counter = itertools.count() | |
#right move | |
if j + 1 < self.env.n and self.env.navigable(i, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-right move | |
'''if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i + 1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry)''' | |
#down move | |
if i + 1 < self.env.m and self.env.navigable(i + 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-left move | |
'''if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry)''' | |
#left move | |
if j - 1 >= 0 and self.env.navigable(i, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-left move | |
'''if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry)''' | |
#up move | |
if i - 1 >= 0 and self.env.navigable(i - 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-right move | |
'''if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry)''' | |
'''for f in nextf: | |
print f.x, f.y, f.cost''' | |
#nextf.sort(key=lambda x: x.cost) | |
return newf | |
def solver(self): | |
start = Node(self.src_i, self.src_j, 0) | |
fringe = [start] | |
visited = [] | |
while fringe: | |
next_fringe = fringe.pop(0) | |
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j): | |
#print "found" | |
return next_fringe.cost | |
#for kk in visited: | |
#print "VIS" , kk.x, kk.y, kk.cost | |
#for kk in fringe: | |
#print "fr" , kk.x, kk.y, kk.cost | |
nextFringes = self.next_fringes(next_fringe) | |
#nextFringes.sort(key = lambda x: x.cost) | |
for newf in nextFringes: | |
if newf[2] not in visited and newf[2] not in fringe: | |
fringe.append(newf[2]) | |
#print newf[1].x, newf[1].y, newf[1].cost | |
'''else: | |
print newf[1].x, newf[1].y, newf[1].cost, "Already"''' | |
visited.append(next_fringe) | |
fringe.sort(key=lambda i: i.total) | |
'''for kkk in fringe: | |
print (kkk.x, kkk.y, kkk.cost, kkk.total)''' | |
##input | |
k = raw_input().split() | |
m = int(k[0]) | |
n = int(k[1]) | |
grid = [] | |
for i in range(m): | |
row = [] | |
row = [int(x) for x in raw_input().split()] | |
grid.append(row) | |
#print grid | |
x = int(raw_input()) | |
query = [] | |
for i in range(x): | |
k = raw_input().split() | |
query.append([(int(k[0]), int(k[1])),(int(k[2]), int(k[3]))]) | |
e = Environment(grid, m, n) | |
for i in range(x): | |
a = Agent(query[i], e) | |
cost = a.solver() | |
cost = int(round(cost)) | |
#print cost | |
if cost % 2 == 0: | |
print (cost/2), (cost/2) | |
else: | |
print (cost/2+1), (cost/2) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# -*- coding: utf-8 -*- | |
""" | |
Created on Fri Sep 04 02:53:49 2015 | |
@author: SAPTAK | |
""" | |
# -*- coding: utf-8 -*- | |
""" | |
Created on Thu Sep 03 10:16:00 2015 | |
@author: SAPTAK | |
""" | |
from math import sqrt | |
import heapq | |
import itertools | |
class Node: | |
def __init__(self, x, y, cost, total=0): | |
self.x = x | |
self.y = y | |
self.cost = cost | |
self.total = total | |
def __eq__(self, other): | |
return (self.x, self.y) == (other.x, other.y) | |
class Environment: | |
def __init__(self, grid, m, n): | |
self.grid = grid | |
self.m = m | |
self.n = n | |
def navigable(self, i, j): | |
if self.grid[i][j] == 0: | |
return True | |
else: | |
return False | |
def get_cost(self, src, dest): | |
(src_i, src_j) = src | |
(dest_i, dest_j) = dest | |
#print str(src), str(dest), sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
return sqrt(pow((src_i - dest_i),2) + pow((src_j - dest_j),2)) | |
class Agent: | |
def __init__(self, query, env): | |
(self.src_i, self.src_j) = query[0] | |
(self.dest_i, self.dest_j) = query[1] | |
self.env = env | |
def heuristic(self, (x, y)): | |
(i, j) = (x, y) | |
return sqrt(pow((i - self.dest_i),2) + pow((j - self.dest_j),2)) | |
def next_fringes(self, present): | |
(i, j) = (present.x, present.y) | |
cost = present.cost | |
newf = [] | |
counter = itertools.count() | |
#right move | |
if j + 1 < self.env.n and self.env.navigable(i, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-right move | |
if j + 1 < self.env.n and i + 1 < self.env.m and self.env.navigable(i + 1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i + 1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i + 1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down move | |
if i + 1 < self.env.m and self.env.navigable(i + 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#down-left move | |
if i + 1 < self.env.m and j - 1 >= 0 and self.env.navigable(i + 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i+1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i+1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#left move | |
if j - 1 >= 0 and self.env.navigable(i, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-left move | |
if j - 1 >= 0 and i - 1 >= 0 and self.env.navigable(i - 1, j - 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j-1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j-1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up move | |
if i - 1 >= 0 and self.env.navigable(i - 1, j): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j, next_cost, total)] | |
heapq.heappush(newf, entry) | |
#up-right move | |
if j + 1 < self.env.n and i-1 >= 0 and self.env.navigable(i-1, j + 1): | |
count = next(counter) | |
next_cost = cost + self.env.get_cost((i, j), (i-1, j+1)) | |
total = next_cost + self.heuristic((i,j)) | |
entry = [total, count, Node(i-1, j+1, next_cost, total)] | |
heapq.heappush(newf, entry) | |
'''for f in nextf: | |
print f.x, f.y, f.cost''' | |
#nextf.sort(key=lambda x: x.cost) | |
return newf | |
def solver(self): | |
start = Node(self.src_i, self.src_j, 0) | |
fringe = [start] | |
visited = [] | |
while fringe: | |
next_fringe = fringe.pop(0) | |
if (next_fringe.x, next_fringe.y) == (self.dest_i,self.dest_j): | |
#print "found" | |
return next_fringe.cost | |
#for kk in visited: | |
#print "VIS" , kk.x, kk.y, kk.cost | |
#for kk in fringe: | |
#print "fr" , kk.x, kk.y, kk.cost | |
nextFringes = self.next_fringes(next_fringe) | |
#nextFringes.sort(key = lambda x: x.cost) | |
for newf in nextFringes: | |
if newf[2] not in visited and newf[2] not in fringe: | |
fringe.append(newf[2]) | |
#print newf[1].x, newf[1].y, newf[1].cost | |
'''else: | |
print newf[1].x, newf[1].y, newf[1].cost, "Already"''' | |
visited.append(next_fringe) | |
fringe.sort(key=lambda i: i.total) | |
'''for kkk in fringe: | |
print (kkk.x, kkk.y, kkk.cost, kkk.total)''' | |
##input | |
k = raw_input().split() | |
m = int(k[0]) | |
n = int(k[1]) | |
grid = [] | |
for i in range(m): | |
row = [] | |
row = [int(x) for x in raw_input().split()] | |
grid.append(row) | |
#print grid | |
x = int(raw_input()) | |
query = [] | |
for i in range(x): | |
k = raw_input().split() | |
query.append([(int(k[0]), int(k[1])),(int(k[2]), int(k[3]))]) | |
e = Environment(grid, m, n) | |
for i in range(x): | |
a = Agent(query[i], e) | |
cost = a.solver() | |
cost = int(round(cost)) | |
#print cost | |
if cost % 2 == 0: | |
print ((cost/2) + (cost/2)) | |
else: | |
print ((cost/2+1) + (cost/2)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment