Thread: maze problem

here is a maze problem
0 indicates - solid cells
1 indicates - empty cells
# indicates starting position
@ indicates ending position

i have written the program assuming there r no loops
but suppose the question is to find the shortest path then...

eg :
# 1 1 1 1
0 0 0 1 0
0 1 0 1 1
0 @ 1 1 1

in this case my prog gives the output 10
which actually should be 8 by getting the path as follows

wrong
# 1 1 1 -
- - - 1 -
- - - 1 1
- @ 1 1 1

right
# 1 1 1 -
- - - 1 -
- - - 1 -
- @ 1 1 -

my strategy is after i visit a cell i replace it by 'x' so that while bactracking it does not go backwards

i am checking neighbours as
note that each cell can go either horizontally or vertically

Code:

int neigh(int *li,int *lj,char c)
{
    int i=*li,j=*lj;
    int ti,tj,isc = 0;
    if((i-1)>=0)
    {
        if(maze[i-1][j]==c)
        {
            ti = i-1;
            tj = j;
            isc = 1;
        }
    }        
    if((j-1)>=0)
    {
        if(maze[i][j-1]==c)
        {
            ti = i;
            tj = j-1;
            isc = 1;
        }
    }        
    if((i+1)<m)
    {
        if(maze[i+1][j]==c)
        {
            ti = i+1;
            tj = j;
            isc = 1;
        }
    }        
    if((j+1)<n)
    {
        if(maze[i][j+1]==c)
        {
            ti = i;
            tj = j+1;
            isc = 1;
        }
    }
    if(isc==1)
    {
        *li = ti;
        *lj = tj;
    }
    return isc;
}

whats wrong?
give me the slightest idea...

Here's an idea: Start at 1, and for every step, make that neighbor be "this cell + 1". If when you're backtracking, you have a neighbor whose number is greater than "here + 1", you know it's shorter to go that way than the way you just went:

Code:

# 1 2 3 4 
0 0 0 4 0
0 1 0 5 6
0 @ 9 8 7

Now, when you backtrack ... 9, 8, 7, 6, 5, ... 5 will see neighbor 8. Since 8 is bigger than 6, it now knows that if it goes there instead, it will be shorter than going the other way. Then, you just renumber the greater of the exits:

Code:

# 1 2 3 4 
0 0 0 4 0
0 1 0 5 6
0 @ 7 6 7

Quzah.