POJ3984《迷宫问题》

题目描述

定义一个二维数组：

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,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input

一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output

左上角到右下角的最短路径，格式如样例所示。

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)

思路

通过广搜，将每个坐标看做图的节点，四个方向看做图的边，所要求的就是从(0, 0) 到(4, 4)的最短路径。

每个坐标的状态分三种，未访问，可访问，已访问。

通过队列来管理，首先将最开始的(0, 0)加入队列。

每个在队列中的坐标都要去判断可访问的坐标。

比如(0, 0)它可以走四个方向。

判断方向是否可以走

1. 不可以

其中上和左是超出边界了，右侧是碰到墙壁。那么就换个方向。

1. 可以
   将当前可以访问的坐标加入到队列中，将当前坐标标记已访问，并判断是否是终点，是，结束，不是，队列向下继续搜索。

代码

#include<iostream>
using namespace std;
struct Node
{
    int x, y, pre;  
}queue[50];

int front = 0;
int rear = 0;

int a[5][5];
int visit[5][5];

int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


void dfs(int beginX, int beginY, int endX, int endY)
{
    queue[0].x = beginX;
    queue[0].y = beginY;
    queue[0].pre = -1;
    rear+=1;
    visit[beginX][beginY]=1;
    while(front < rear)
    {
        for(int i = 0; i < 4; i++)
        {
            int nowX = queue[front].x + dir[i][0];
            int nowY = queue[front].y + dir[i][1];
            if(nowX < 0 || nowX > 5 || nowY < 0 || nowY > 5 || a[nowX][nowY] == 1 || visit[nowX][nowY] == 1)
            {
                continue;
            }
            queue[rear].x = nowX;
            queue[rear].y = nowY;
            queue[rear].pre = front;    
            rear++;
            visit[nowX][nowY] = 1;
            if(nowX == endX && nowY == endY)
                return;
        }
        front++;
    }
}

void print(Node past)
{
    if(past.pre == -1)
        cout<<"("<<past.x<<", "<<past.y<<")"<<endl;  
    else
    {
        print(queue[past.pre]);
        cout<<"("<<past.x<<", "<<past.y<<")"<<endl;  
    }
}


int main()
{

    for(int i = 0; i < 5; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            cin>>a[i][j];
        }
    }
    dfs(0, 0, 4, 4);
    print(queue[rear-1]);
    return 0;
}