Q - 迷宫问题 POJ - 3984(BFS / DFS + 记录路径)

Q - 迷宫问题 POJ - 3984

定义一个二维数组：

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)

题解一

//深搜版

#include<iostream>

#include<stack>

using namespace std;

const int Len = 5;

int map[Len][Len];

int mark[Len][Len];

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

int s_x = 0,s_y = 0,e_x = 4,e_y = 4;

struct Node

{

    int x,y;

}tem;

stack<Node> st;

bool is_good(int x,int y)

{

    if(x >= 0 && y >= 0 && x < 5 && y < 5 && ! mark[x][y] && map[x][y] != 1)

        return true;

    return false;

}

int flag = 0;

void dfs(int x,int y)

{

    if(x == e_x && y == e_y)

    {

        flag = 1;

        //printf("(%d,%d)\n",x,y);

        tem.x = x,tem.y = y;

        st.push(tem);

        return;

    }

    for(int i = 0; i < 4; i ++)

    {

        int xx = x + mov[i][0];

        int yy = y + mov[i][1];

        if(is_good(xx , yy))

        {

            mark[xx][yy] = 1;

            dfs(xx , yy);

            if(flag ==  1)

            {

                //printf("(%d,%d)\n",x,y);

                tem.x = x,tem.y = y;

                st.push(tem);

                return;

            }

            mark[xx][yy] = 0;

        }

    }

}

int main()

{

    //freopen("T.txt","r",stdin);

    for(int i = 0; i < Len; i ++)

        for(int j = 0; j < Len; j ++)

            scanf("%d", &map[i][j]);

    dfs(s_x,s_y);

    while(! st.empty())

    {

        tem = st.top();

        st.pop();

        if(!st.empty())

            printf("(%d, %d)\n",tem.x,tem.y);

        else

            printf("(%d, %d)",tem.x,tem.y);

    }

    return 0;

}

题解二

//深搜版

#include<iostream>

#include<queue>

#include<stack>

using namespace std;

const int Len = 5;

int map[Len][Len];

int mark[Len][Len];

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

int s_x = 0,s_y = 0,e_x = 4,e_y = 4;

struct Node

{

    int x,y;

}tem,s,e,node[Len][Len];

stack<Node> st;

queue<Node> q;

bool is_good(int x,int y)

{

    if(x >= 0 && y >= 0 && x < 5 && y < 5 && ! mark[x][y] && map[x][y] != 1)

        return true;

    return false;

}

int flag = 0;

void print(int x,int y)

{

    if(node[x][y].x == x && node[x][y].y == y)

    {

        printf("(%d, %d)\n",x,y);

        return;

    }

    print(node[x][y].x , node[x][y].y);

        printf("(%d, %d)\n",x,y);

}

void bfs()

{

    //初始化、赋值、做标记、压队列

    s.x = s_x;

    s.y = s_y;

    node[s.x][s.y].x = s.x;

    node[s.x][s.y].y = s.y;

    mark[s.x][s.y] = 1;

    q.push(s);

    while(! q.empty())

    {

        s = q.front();

        q.pop();

        if(s.x == e_x && s.y == e_y)

        {

            print(s.x , s.y);

            return;

        }

        for(int i = 0; i < 4; i ++)

        {

            e.x = s.x + mov[i][0];

            e.y = s.y + mov[i][1];

            if(is_good(e.x , e.y))

            {

                node[e.x][e.y].x = s.x;

                node[e.x][e.y].y = s.y;

                mark[e.x][e.y] = 1;

                q.push(e);

            }

        }

    }

}

int main()

{

    //freopen("T.txt","r",stdin);

    for(int i = 0; i < Len; i ++)

        for(int j = 0; j < Len; j ++)

            scanf("%d", &map[i][j]);

    bfs();

    return 0;

}