迷宫最短路径问题

 1 #include<iostream>
 2 #include<queue>
 3 #include<memory.h>
 4 using namespace std;
 5 
 6 char map[100][100];
 7 int n, m;
 8 
 9 struct Point {
10     int x, y;
11     Point(int x = 0, int y = 0) : x(x), y(y) {}
12 };
13 
14 struct Node {
15     Point p;
16     int len;
17     Node(const Point &p, int len) : p(p), len(len) {}
18 };
19 
20 bool isValid(const Point &p) {
21     return p.x >= 0 && p.y < n && p.y >= 0 && p.y < n && map[p.x][p.y] == ‘.‘;
22 }
23 
24 int minDistance(const Point &s, const Point &d) {
25     int dir[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
26     bool visited[100][100];
27     memset(visited, false, sizeof(visited));
28     queue<Node> q;
29     q.push(Node(s, 0));
30     visited[s.x][s.y] = true;
31     while (!q.empty()) {
32         Node n = q.front();
33         if (n.p.x == d.x && n.p.y == d.y) {
34             return n.len;
35         }
36         q.pop();
37         for (int i = 0; i < 4; ++i) {
38             Point p(n.p.x + dir[i][0], n.p.y + dir[i][1]);
39             if (isValid(p) && !visited[p.x][p.y]) {
40                 q.push(Node(p, n.len + 1));
41                 visited[p.x][p.y] = true;
42             }
43         }
44     }
45     return -1;
46 }
47 
48 void buildMap(void) {
49     cin >> n >> m;
50     for (int i = 0; i < n; ++i) {
51         for (int j = 0; j < m; ++j) {
52             cin >> map[i][j];
53         }
54     }
55 }
56 
57 int main(void) {
58     buildMap();
59     Point s, d;
60     cin >> s.x >> s.y >> d.x >> d.y;
61     cout << minDistance(s, d);
62     return 0;
63 }