1086.迷宫问题

Description
定义一个二维数组：

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 <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

struct node
{
    int x, y, pre, prex, prey;
} a[125];

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
int mp[10][10];
bool vis[10][10];

struct answer
{
    int aimx, aimy;
} ans[125];
int aimx[25];
int aimy[25];
int fro, bac;

void print(int i, int j);

void bfs(int x, int y)
{
    fro = 0;
    bac = 1;
    a[fro].x = x;
    a[fro].y = y;
    a[fro].pre = -1;
//    a[fro].prex = -1;
//    a[fro].prey = -1;
    vis[x][y] = 1;
    while(fro < bac)///小小的设计体现了队列的先进先出、穷竭搜索！
    {
        for(int i = 0; i < 4; ++i)
        {
            int temx = a[fro].x + dx[i];
            int temy = a[fro].y + dy[i];
            if(temx < 0 || temy < 0 || temx >= 5 || temy >= 5 || vis[temx][temy])
                continue;
            vis[temx][temy] = 1;
            a[bac].x = temx;
            a[bac].y = temy;
            a[bac].pre = fro;
            a[bac].prex = a[fro].x;
            a[bac].prey = a[fro].y;
            bac++;

            if(temx == 4 && temy == 4)
            {
                print(fro, bac - 1);
                return ;
            }
        }
        fro++;
    }
    return ;
}

void print(int i, int j)
{
//    cout << i << ' ' << j << '\n';
    int tem = i;
    int len = 0;
    aimx[len] = a[j].x;
    aimy[len] = a[j].y;
    len++;
    while(a[tem].pre != -1)
    {
//        cout << tem << ' ' << a[tem].x << ' ' << a[tem].y << '\n';
        aimx[len] = a[tem].x;
        aimy[len] = a[tem].y;
        len++;
        tem = a[tem].pre;
    }
//    cout << len << '\n';
    ///存了倒序的路径，自然要倒序输出
    for(int k = len - 1; k >= 0; --k)
    {
        printf("(%d, %d)\n", aimx[k], aimy[k]);
    }
    cout << '\n';
}

int main()
{
    for(int i = 0; i < 5; ++i)
    {
        for(int j = 0; j < 5; ++j)
        {
            cin >> mp[i][j];
            if(mp[i][j] == 1)
            {
                vis[i][j] = 1;
    ///我傻了，写这里的时候，赋值语句跟着上面用了==
            }
        }
    }
    printf("(0, 0)\n");
//    for(int i = 0; i < 5; ++i)
//    {
//        for(int j = 0; j < 5; ++j)
//        {
//            cout << mp[i][j] << ' ' << vis[i][j] << ' ' ;
//        }
//        cout << '\n';
//    }
    bfs(0, 0);
    return 0;
}