Maze 解题报告

　　　　　　　　　　　　　　　Maze

Description

You are given a special Maze described as an n*m matrix, please find the shortest path to reach (n,m) from (1,1);

Input

The first line of the input is an integer T (T <= 100), which stands for the number of test cases you need to solve.

Each test case begins with two integers n, m (1 <= n, m <= 250) in the first line indicating the size of the board. Then n lines follow, each line contains m numbers either 0 or 1 which are:
0 : represents a grid on which you can step.
1 : represents a wall.

Output

For every test case, you should output "Case #k: " first, where k indicates the case number and starts at 1. If it’s impossible to reach the end position, just output “-1”. Otherwise, output the minimum number of steps to solve this problem.

Sample Input

1
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

Sample Output

Case #1: 8

这题据说是2011 UESTC Training for Search Algorithm——A，不过我找不到原题，所以不知道自己写的能不能过。觉得该题是最好的BFS入门题啦。

这是我第一次写BFS，纪念一下^_^

题目意思就是找出从点（1， 1）到点(n, m) 的距离最短是多少。注意格子是 0 的点才能走，1代表墙，是不能走的。

因为BFS 是逐层拓展的，不像DFS 一直往深处找，所以能保证当达到点(n, m) 时即找到最短的距离。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <queue>

using namespace std;

const int maxn =  + ;

struct node

{

    int x;

    int y;

    int step;

};

int maze[maxn][maxn];

int dx[] = {, , , -};

int dy[] = {, , -, };

int main()

{

    int T, n, m;

    while (scanf("%d", &T) != EOF)

    {

        for (int cas = ; cas <= T; cas++)

        {

            scanf("%d%d", &n, &m);

            for (int i = ; i <= n; i++)

            {

                for (int j = ; j <= m; j++)

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

            }

            int ans = ;

            queue<node> q;

            q.push({, , });  // 代表从坐标点(1, 1)出发

            while (!q.empty())

            {

                node cur = q.front();  // 取出队首元素

                q.pop();

                int cur_x = cur.x;

                int cur_y = cur.y;

                if (cur_x == n && cur_y == m)  // 到达目标节点

                {

                    ans = cur.step;     // 得到最短步数

                    break;

                }

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

                {

                    int tx = cur_x + dx[i];

                    int ty = cur_y + dy[i];

                    if (tx >=  && tx <= n && ty >=  && ty <= m && !maze[tx][ty])  // 可以走且没有走过

                    {

                        maze[tx][ty] = ;

                        q.push({tx, ty, cur.step+});

                    }

                }

            }

            printf("Case #%d: %d\n", cas, ans);

        }

    }

    return ;

}

巴特西