Poj 3984 maze problem (extensive search + output path)

Description

Define a 2D array:

int maze[5][5] = {

	0, 1, 0, 0, 0,

	0, 1, 0, 1, 0,

	0, 0, 0, 0, 0,

	0, 1, 1, 1, 0,

	0, 0, 0, 1, 0,

};

It represents a maze, in which 1 represents the wall, 0 represents the path that can be walked, can only walk horizontally or vertically, can't walk obliquely, and requires programming to find the shortest path from the upper left corner to the lower right corner.

Input

A 5 × 5 two-dimensional array represents a maze. Data guarantees a unique solution.

Output

The shortest path from the upper left corner to the lower right corner, in the format shown in the example.

Sample Input

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

Train of thought:

Guang Shu. Record the last point through path[i][j] is the path reached by road[i] [J], and push back through path[i][j].

Reference code:

#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
using namespace std;

typedef struct point
{
    int x, y;
} P;
const int N = 5;

// m storage maze
int m[N][N], road[4][2]= {0,-1,0,1,-1,0,1,0}, vis[N][N];
// The last point recorded through path[i][j] is reached through road[i] []
// Push back the path through path[i][j]
int path[N][N];
queue <P> Q;

void bfs(P now)
{
    Q.push(now);
    vis[now.x][now.y] = 1;

    while(!Q.empty())
    {
        now =Q.front();
        Q.pop();

        if(now.x==4 && now.y== 4)
            return ;

        for(int i=0; i<4; i++)
        {
            P tem;
            tem.x = now.x + road[i][0], tem.y = now.y + road[i][1];
            if((tem.x>=0&&tem.x<N&&tem.y>=0&&tem.y<N) && vis[tem.x][tem.y] == 0 && m[tem.x][tem.y] == 0)
            {
                Q.push(tem);
                path[tem.x][tem.y]= i;
                vis[tem.x][tem.y] = 1;
            }
        }

    }
}

int main()
{
    int i, j;

    // Input labyrinth
    for(i=0; i<N; i++)
        for(j=0; j<N; j++)
            scanf("%d",&m[i][j]);

    P now;
    now.x = 0, now.y = 0;

    // Initialization
    memset(vis, 0, sizeof(vis));
    memset(path, 0, sizeof(path));

    bfs(now);
    now.x = 4, now.y = 4;

    int k = 0;
    P step[100];
    while(1)
    {
        step[++k] = now;
        if(now.x == 0 && now.y == 0)
            break;
        int temp = path[now.x][now.y];

        now.x -= road[temp][0];
        now.y -= road[temp][1];
    }

    for(int i=k; i>=1; i--)
    {
        printf("(%d, %d)\n",step[i].x,step[i].y);
    }
    return 0;
}

 

Tags: Programming

Posted on Sat, 09 Nov 2019 10:28:33 -0800 by diex