Hello,
I've tried using BFS for this problem but am having trouble.
http://code.google.com/codejam/contest/186264/dashboard#s=p2
After I get one path for minimal solution, [from bfs] I need to fully
search for all solutions in the bfs, [by looking at number of steps]
but am not able to do it.
In the code, (shown below) x is the minimal number of steps to reach
the i,j th position. Now I want to look till the x + 1th step - tried
to implement another bfs, but that runs very slow.
My code in Python - this basically does BFS, but need to go further
down and better (This will return one path ending at the i,j th
position, with minimal steps)
*************************************************************************
from collections import deque
class Square:
def __init__ (self, x = 0, y = 0, s = 0, a = 0, b = None):
self.X = x
self.Y = y
self.sum = s
self.steps = a
self.square = b
def SquareMath(i,j,a,target): # l is the Square that we're looking
at, i,j are the positions
a[0] = list(map(int,(a[0].split(' '))))
l = a[1:]
m = []
q = deque()
start = Square(i,j,int(l[i][j]),0)
#Square is of type (x,y, sum,steps,square)
q.append(start)
sum1 = 0
y = 0
p = []
c = False
#Now its the standard BFS algorithm
while len(q) != 0:
top = q[0]
q.popleft()
for direction1 in [[1,0],[-1,0],[0,1],[0,-1]]:
for direction2 in [[1,0],[-1,0],[0,1],[0,-1]]:
i,j = direction1[0],direction1[1]
u,v = direction2[0],direction2[1]
new_X = top.X + i
new_Y = top.Y + j
if new_X <= len(l)-1 and new_X >= 0 and new_Y <=
len(l)-1 and new_Y >= 0:
t = Square(new_X,new_Y,top.sum,top.steps,top)
new2_X = new_X + u
new2_Y = new_Y + v
if new2_X <= len(l)-1 and new2_X >= 0 and new2_Y
<= len(l)-1 and new2_Y >= 0:
s = 0
if l[new_X][new_Y] == '+':
s = top.sum + int(l[new2_X][new2_Y])
q.append(Square(new2_X,new2_Y,s,top.steps
+ 1,t))
if top.sum == target:
return top.steps + 1
elif l[new_X][new_Y] == '-':
s = top.sum - int(l[new2_X][new2_Y])
q.append(Square(new2_X,new2_Y,s,top.steps
+ 1,t))
if top.sum == target:
return top.steps + 1
if top.sum == target: #and c == False:
x = top.steps + 1
path = []
t2 = top
path = path + [l[top.X][top.Y]]
while top.square != None:
t1 = top.square
path = path + [l[t1.X][t1.Y]]
top = top.square
s = ''.join([i for i in path])
p = p + [[s,x]]
return p
**********************************************************************
Any ideas/ suggestions?
Thanks alot :)
--
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en.
