迷宫最短路径问题

问题描述：给定一个迷宫和一个起点一个终点，求起点到终点的最短路径长度。

Sample Input

(说明：5行5列的迷宫，‘#’为墙，‘.’为路，起点为(0,3), 终点为(4,4))

Sample Output

11

(若不可达输出-1)

解答：用BFS的方法，借助一个队列实现。

#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;

char map[100][100];
int n, m;

struct Point {
    int x, y;
    Point(int x = 0, int y = 0) : x(x), y(y) {}
};

struct Node {
    Point p;
    int len;
    Node(const Point &p, int len) : p(p), len(len) {}
};

bool isValid(const Point &p) {
    return p.x >= 0 && p.y < n && p.y >= 0 && p.y < n && map[p.x][p.y] == '.';
}

int minDistance(const Point &s, const Point &d) {
    int dir[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
    bool visited[100][100];
    memset(visited, false, sizeof(visited));
    queue<Node> q;
    q.push(Node(s, 0));
    visited[s.x][s.y] = true;
    while (!q.empty()) {
        Node n = q.front();
        if (n.p.x == d.x && n.p.y == d.y) {
            return n.len;
        }
        q.pop();
        for (int i = 0; i < 4; ++i) {
            Point p(n.p.x + dir[i][0], n.p.y + dir[i][1]);
            if (isValid(p) && !visited[p.x][p.y]) {
                q.push(Node(p, n.len + 1));
                visited[p.x][p.y] = true;
            }
        }
    }
    return -1;
}

void buildMap(void) {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> map[i][j];
        }
    }
}

int main(void) {
    buildMap();
    Point s, d;
    cin >> s.x >> s.y >> d.x >> d.y;
    cout << minDistance(s, d);
    return 0;
}