NOJ1042——算法实验三——电子老鼠闯迷宫

电子老鼠闯迷宫

描述：

有一只电子老鼠被困在如下图所示的迷宫中。这是一个12*12单元的正方形迷宫，黑色部分表示建筑物，白色部分是路。电子老鼠可以在路上向上、下、左、右行走，每一步走一个格子。现给定一个起点S和一个终点T，求出电子老鼠最少要几步从起点走到终点。

输入：

本题包含一个测例。在测例的第一行有四个由空格分隔的整数，分别表示起点的坐标S（x.y）和终点的坐标T（x,y）。从第二行开始的12行中，每行有12个字符，描述迷宫的情况，其中’X’表示建筑物，’.'表示路.

输出：

输出一个整数，即电子老鼠走出迷宫至少需要的步数。

输入样例：

2 9 11 8
XXXXXXXXXXXX
X…X.XXX
X.X.XX…X
X.X.XX.XXX.X
X.X…X…X
X.XXXXXXXXXX
X…X.X…X
X.XXX…XXXX
X…X…X
XXX.XXXX.X.X
XXXXXXX…XXX
XXXXXXXXXXXX

输出样例：

28

源代码

#include <iostream>
#include <queue>
using namespace std;
int walk[4][2] = {
    1,0,
    0,1,
    -1,0,
    0,-1
};
int maze[12][12];
int step[12 * 12];
void input()
{
    int i, j;
    char c;
    for (i = 0; i < 12; i++)
    {
        for (j = 0; j < 12; j++)
        {
            cin >> c;
            if(c == 'X')
                maze[i][j] = 1;
        }
    }
}
int make_new_place(int row,int col,int type)
{
    row += walk[type][0];
    col += walk[type][1];
    if(row < 0 || row >= 12 || col < 0 || col >= 12)
    {
        return -1;
    }
    if(maze[row][col] != 0)
        return -1;
    else
        return row * 12 + col;
}
void bfs(queue<int> q,int end_r,int end_c)
{
    int i;
    while(!q.empty())
    {
        int pop_num = q.front();
        q.pop();
        int place_r = pop_num / 12;
        int place_c = pop_num % 12;
        int new_num[4];
        for (i = 0; i < 4; i++)
        {
            new_num[i] = make_new_place(place_r, place_c, i);
            if(new_num[i] != -1)
            {
                step[new_num[i]] = step[pop_num] + 1;
                int row = new_num[i] / 12;
                int col = new_num[i] % 12;
                maze[row][col] = pop_num;
                q.push(new_num[i]);
                if(row == end_r && col == end_c)
                {
                    return;
                }
            }
        }
    }
}
int main()
{
    queue<int> q;
    int begin_x, begin_y;
    int end_x, end_y;
    cin >> begin_x >> begin_y;
    cin >> end_x >> end_y;
    input();
    q.push((begin_x - 1) * 12 + (begin_y - 1));
    maze[begin_x - 1][begin_y - 1] = 1;
    bfs(q, end_x - 1, end_y - 1);
    cout << step[(end_x - 1) * 12 + (end_y - 1)] << endl;
}

思路

之前用深搜也写过迷宫问题，不过广搜是为了找到最短路径，而且找到一条最优解后就可以退出。
扩展新结点的时候只需要判断是否越界，撞墙，重复，如果都没有，那么返回行*12+列就可以得到扩展结点的位置。

1. 出队元素，扩展四个结点，若返回值不为-1，则入队。
2. 如果入队元素的横纵坐标为目标点就返回。

这道题和其他题稍有不同，它的坐标是从1开始的，这是需要注意的。