Grid problem

[ajhais]

Given a n*n grid with free spaces and obstacles in the form an n*n integer matrix. We need to find shortest between any two given points (x1,y1) and (x2,y2) through the free spaces. We are not allowed to move in diagonal. Please help me figuring out an algorithm for doing this.
Thanks in advance.

[csurfer]

Given a n*n grid with free spaces and obstacles in the form an n*n integer matrix. We need to find shortest between any two given points (x1,y1) and (x2,y2) through the free spaces. We are not allowed to move in diagonal. Please help me figuring out an algorithm for doing this. Thanks in advance.

Well this is one of the many ideas you can apply to this problem.Here it goes:

Firstly take the value of n for your n*n grid from the user and also a valid grid structure input where free spaces are represented by 1's and obstacles are represented by 0's.

Your array for 4*4 might look like this:

0 1 2 3
0  1 1 0 0
1  0 1 0 0  
2  1 1 1 1
3  0 1 1 1

Now pass this array as input array and (x1,y1) as input co-ordinate
and (x2,y2) as the destination point to be reached for a "DEPTH FIRST CHECK" graph algorithm.

Actually the best graph algorithm to find the shortest path between two vertices is "DIJKSTRA'S ALGORITHM" but here as you are just moving one step to top bottom left or right only and all steps are of same length you can use Depth First Search only to solve your problem.

[ajhais]

Well this is one of the many ideas you can apply to this problem.Here it goes:

Firstly take the value of n for your n*n grid from the user and also a valid grid structure input where free spaces are represented by 1's and obstacles are represented by 0's.

Your array for 4*4 might look like this:

0 1 2 3
0  1 1 0 0
1  0 1 0 0  
2  1 1 1 1
3  0 1 1 1

Now pass this array as input array and (x1,y1) as input co-ordinate and (x2,y2) as the destination point to be reached for a "DEPTH FIRST CHECK" graph algorithm.

Actually the best graph algorithm to find the shortest path between two vertices is "DIJKSTRA'S ALGORITHM" but here as you are just moving one step to top bottom left or right only and all steps are of same length you can use Depth First Search only to solve your problem.

Hi.. thanks for the solution. I was thinking of going with the same.. How can we approach this problem if the map is dynamic.. that is if some obstacles can randomly appear in the map.. We actually need to code a bot for battle city game..

[csurfer]

Hi.. thanks for the solution. I was thinking of going with the same.. How can we approach this problem if the map is dynamic.. that is if some obstacles can randomly appear in the map.. We actually need to code a bot for battle city game..

Well if you know DFSearch then you will know that each time the whole array gets passed as one of the function argument to the recursive DFSearch function and checking is done in a for loop.
So before checking in the for loop in case of dynamic obstacles just change the particular

Array[][] = 0;

before passing the array to next DFS function recursively.

[nucleon]

ajhais,
It should actually be a Breadth First Search (BFS), not a DFS.

[csurfer]

ajhais, It should actually be a Breadth First Search (BFS), not a DFS.

No its a DFS only not BFS : You don't need to move to all points adjoining a point,if you wanted to do that then BFS is required. But in this problem we want to move through different blocks taking steps moving away from start point so we need DFS where once we reach a point then we need to take a step towards destination not worrying about the other points reachable from that point.
After all evaluation we need to find the shortest path.

[nucleon]

I don't feel like arguing. Can someone else weigh in on this? DFS or BFS?

[Prabakar]

If you know that there is a way, why not go for it, why should one try all the ways possible? If you are lucky you would have chose the right path the first time. I would go for DFS. I believe one should use a stack and not queue.