[amitchhajer]

I am quite decent with algorithms and can make my own logic most of the times. Twice this year i was not able to win competitions only because of maze related problem. People say they are easy but i never found way how to start them,, if i have solved same problem before then i can, else
for eg: today i had a simple problem( some of friends solve it in no time)

You have been given with a N x N matrix(constraint 20) and it is to be filled with 0's(zero) and 1's(one) by user. A zero means you can step on it and one means not allowed. So i had to find a path from (0,0) to (N,N) both of which are zero (to be assumed).

test case
0 1 0 0
0 1 0 1
0 0 0 1
1 1 0 0

so possible path is 0,0-> 1,0-> 2,0-> 2,1-> 2,2-> 3,2-> 3,3

there are many similar problems, i am not able to approach them. help me out how to do these types of problem, i need the approach

[IngeniousHax]

how about a checkLeft(); and checkDown(); and checkRight(); and checkUp();... Since you are, in this example, trying to find your way through a maze in an NxN matrix you could always just check to see whether there is a 1 or not for a next move and base your next move on the most likely candidate?

[Nikitin]

It's a simple backtracking exercise. Look it up for more info.

[mostyfriedman]

this is a very simple backtracking exercise as already mentioned. When solving these kind of things its best to keep the body of the recursive method as clean and as abstract as possible, any implementation details should be moved to other methods. Here's a quick sketch of how to brute force it.

Solve(matrix, xpos, ypos):-
if xpos == N AND ypos == N
return

if canGoDown(matrix, xpos, ypos) == True
Solve(matrix, xpos, ypos+1)

if canGoUp(matrix, xpos, ypos) == True
Solve(matrix, xpos, ypos-1)

if canGoRight(matrix, xpos, ypos) == True
Solve(matrix, xpos+1, ypos)

if canGoLeft(matrix, xpos, ypos) == True
Solve(matrix, xpos-1, ypos)


and that's it.

This post has been edited by mostyfriedman: 21 February 2011 - 12:33 PM