All geek questions in one place

How to find the fastest route in the maze (in C)

A maze is defined as a square matrix. For example:

int maze[N][N] =
  { { 1, 1, 1, 1, 1, 1, 1 },
    { 0, 1, 0, 1, 0, 0, 1 },
    { 0, 1, 0, 1, 1, 1, 1 },
    { 0, 1, 0, 0, 0, 1, 1 },
    { 0, 1, 1, 1, 0, 1, 1 },
    { 0, 0, 1, 0, 1, 1, 1 },
    { 1, 1, 1, 1, 0, 1, 1 } };

You can only walk where there is 1. You can take a step down, up, left, right. You start in the upper left corner and end in the lower right corner.

Exit should be the minimum step to complete any maze. We can assume that there is at least one way to finish the maze. I edited the code and I thought I covered everything .. but obviously, I am missing something. thanks for the help

int path_help(int maze[][N], int row, int col, int count)
{
    int copy1[N][N], copy2[N][N], copy3[N][N];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            copy1[i][j] = maze[i][j];
            copy2[i][j] = maze[i][j];
            copy3[i][j] = maze[i][j];
        }
    }
    int a, b, c, d;
    if (col == 0 || row == 0)
    {
        if (row == N - 1)
        {
            if (maze[row][col + 1] == 1)
            {
                maze[row][col] = 0;
                return path_help(maze, row, col + 1, count + 1);
            }
            else return N*N;
        }
        if (col == N - 1)
        {
            if (maze[row + 1][col] == 1)
            {
                maze[row][col] = 0;
                return path_help(maze, row + 1, col, count + 1);
            }
            else return N*N;
        }
        if (maze[row][col + 1] == 1 && maze[row + 1][col] == 1)
        {
            maze[row][col] = 0;
            copy1[row][col] = 0;
            return min(path_help(copy1, row, col + 1, count + 1),path_help(maze, row + 1, col, count + 1));
    }
    if (maze[row][col + 1] == 0 && maze[row + 1][col] == 1)
    {
        maze[row][col] = 0;
        return path_help(maze, row + 1, col, count + 1);
    }
    if (maze[row + 1][col] == 0 && maze[row][col + 1] == 1)
    {
        maze[row][col] = 0;
        return path_help(maze, row, col + 1, count + 1);
    }
    else return N*N;
}
if (col == N - 1 || row == N - 1)
{
    if (col == N - 1 && row == N - 1) return count;
    if (row == N - 1)
    {
        if (maze[row - 1][col] == 1 && maze[row][col + 1] == 1)
        {
            maze[row][col] = 0;
            copy1[row][col] = 0;
            return min(path_help(copy1, row, col + 1, count + 1), path_help(maze, row - 1, col, count + 1));
        }

        if (maze[row - 1][col] == 0 && maze[row][col + 1] == 1)
        {
            maze[row][col] = 0;
            return path_help(maze, row, col + 1, count + 1);
        }
        if (maze[row][col + 1] == 0 && maze[row - 1][col] == 1)
        {
            maze[row][col] = 0;
            return path_help(maze, row - 1, col, count + 1);
        }
        else return N*N;
    }
    if (col == N - 1)
    {
        if (maze[row + 1][col] == 1 && maze[row][col - 1] == 1)
        {
            maze[row][col] = 0;
            copy1[row][col] = 0;
            return min(path_help(copy1, row, col - 1, count + 1), path_help(maze, row + 1, col, count + 1));
        }

        if (maze[row + 1][col] == 0 && maze[row][col - 1] == 1)
        {
            maze[row][col] = 0;
            return path_help(maze, row, col - 1, count + 1);
        }
        if (maze[row][col - 1] == 0 && maze[row + 1][col] == 1)
        {
            maze[row][col] = 0;
            return path_help(maze, row + 1, col, count + 1);
        }
        else return N*N;
    }
}
if (maze[row + 1][col] == 1)
{
    maze[row][col] = 0;
    a = path_help(maze, row + 1, col, count + 1);
}
else a = N*N;
if (maze[row - 1][col] == 1)
{
    copy1[row][col] = 0;
    b = path_help(copy1, row - 1, col, count + 1);
}
else b = N*N;
if (maze[row][col + 1] == 1)
{
    copy2[row][col] = 0;
    c = path_help(copy2, row, col + 1, count + 1);
}
else c = N*N;
if (maze[row][col - 1] == 1)
{
    copy3[row][col] = 0;
    d = path_help(copy3, row, col - 1, count + 1);
}
else d = N*N;
return min(min(a, b),min( c, d));

}

+1
source share
3 answers

, @Jackson, , , . 0 no-go, 1 - .

, neigh() , , , 4 . , : , O (!). , : , .

#include <stdio.h>
#include <stdio.h>
#include <limits.h>

#define MSIZE  7                            // matrix/maze dims

enum ntype { virgin, listed, visited };     // for status field

typedef struct {
    int x;                                  // grid position of node
    int y;                                  // grid position of node
    int value;                              // 0 or 1 as defined in maze[][]
    int dist;                               // distance from start node
    int status;                             // enum as above
} node_t;

int maze[MSIZE][MSIZE] =                     // maze definition
  { { 1, 1, 1, 1, 1, 1, 1 },
    { 0, 1, 0, 1, 0, 0, 1 },
    { 0, 1, 0, 1, 1, 1, 1 },
    { 0, 1, 0, 0, 0, 1, 1 },
    { 0, 1, 1, 1, 0, 1, 1 },
    { 0, 0, 1, 0, 1, 1, 1 },
    { 1, 1, 1, 1, 0, 1, 1 } };

node_t node [MSIZE][MSIZE];                 // working array
node_t *list[MSIZE*MSIZE];                  // array of current node pointers
int listlen;                                // num elements in list[]

void neigh(node_t *cptr, int dx, int dy)
// examine one neighbour of node cptr, offset by dx,dy
{
    node_t *nptr;                           // pointer to neighbour
    int dist;                               // accumulated distance from start
    int x = cptr->x + dx;                   // work out neighbour coords
    int y = cptr->y + dy;                   // work out neighbour coords
    if (x < 0 || x >= MSIZE || y < 0 || y >= MSIZE)
        return;                             // failed edge test    
    nptr = &node[y][x];                     // point to neighbour
    if (nptr->value == 0)                   // no-go node
        return;
    if (nptr->status == visited)            // do no re-visit
        return;

    dist = cptr->dist + nptr->value;        // accumulate distance from start
    if (dist < nptr->dist)                  // if it less than what was known...
        nptr->dist = dist;                  // ...update with the new distance
    if (nptr->status == virgin) {           // if it never been seen...
        list[listlen++] = nptr;             // ... neighbour to list
        nptr->status = listed;              // and set its status
    }
}

int main(void)
{
    int i, j, smallest, smallind;
    node_t *cptr, *eptr;

    // init the struct array
    for (j=0; j<MSIZE; j++) {
        for (i=0; i<MSIZE; i++) {
            cptr = &node[j][i];             // pointer to the array element
            cptr->value = maze[j][i];       // the maze definition
            cptr->x = i;                    // self position
            cptr->y = j;                    // self position
            cptr->dist = INT_MAX;           // distance from start (unknown)
            cptr->status = virgin;          // never examined
        }
    }

    eptr = &node[MSIZE-1][MSIZE-1];         // pointer to end node

    cptr = &node[0][0];                     // pointer to start node
    cptr->dist  = 0;                        // distance of start node from itself!

    // main loop
    while (cptr != eptr) {                  // until we reach the target node
        cptr->status = visited;             // we've been here now
        neigh(cptr,  0, -1);                // examine node above
        neigh(cptr, -1, 0);                 // examine node on left
        neigh(cptr,  1, 0);                 // examine node on right
        neigh(cptr,  0, 1);                 // examine node below

        // find smallest distance of nodes in list[] (won't include virgins)
        smallest = INT_MAX;
        smallind = -1;                      // set invalid marker index
        for (i=0; i<listlen; i++) {
            if (smallest > list[i]->dist) { // compare distance with smallest
                smallest = list[i]->dist;   // remembers the smallest
                smallind = i;               // remembers the list index of smallest
            }
        }
        // take smallest for next time and remove from list
        if(smallind < 0) {                  // -1 was the "marker"
            printf("No route found\n");
            return 1;
        }
        cptr = list[smallind];              // smallest becomes current node
        if (listlen)                        // replace in list with last element...
           list[smallind] = list[--listlen];// ... and reduce list length
    }                                       // now examine this node

    printf("Distance = %d\n", eptr->dist);  // show the distance of the end node
    return 0;
}

:

Distance = 12

. , , . .

3 , maze[][] - , . node[][] struct, . , - , , , , .

list[] node[][]. node[][] x,y : , . 1-D , list[], . , , "".

. main(), // init the struct array, , , struct, . , , cptr->x = i;, , node[j][i].x = i;.

+3

, . , , , .

, , " " , . .

, . , , . .

0

, , .

int path_helper(int maze[][N],int height, int width, int row, int col){
  if(row==height-1 && col == width-1) return 0;
  if(maze[row][col]==0) return height*width;
  if(col<0 || row<0 || row>=height || col>=width) return height*width;
  maze[row][col]=0;
  int maze2[7][7]={{0}};
  for(int i = 0; i < height; i++){
    for(int j = 0; j < width; j++)
      maze2[j][i]=maze[j][i];
  }
  return min(min(path_helper(maze2,height,width,row+1,col),
  path_helper(maze2,height,width,row-1,col)),      min(path_helper(maze2,height,width,row,col+1),path_helper(maze2,height,width,row,col-1)))+1;
}

,

0
source

Source: https://habr.com/ru/post/1625351/

More articles:


All Articles