迷宫问题

àì夳堔傛蜴生んèń 2022-08-06 05:07 169阅读 0赞

迷宫问题：以一个m\*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论，如果有通道，请输出最短路径的通道。例如：

0 0 1 0 0 0 1 0

0 0 1 0 0 0 0 0

0 0 0 0 1 1 1 0

0 1 1 1 0 0 1 0

0 0 0 1 0 0 0 0

0 1 0 0 0 1 0 1

0 1 1 1 1 0 0 1

1 1 0 0 0 0 0 1

1 1 0 0 0 0 0 0

思路：利用广度优先搜索

\#include<iostream>  
\#include<queue>  
\#include<iomanip>  
using namespace std;  
struct point \{  
    int x;  
    int y;  
\};  
  
int list\[4\]\[2\] = \{ -1, 0, 1, 0, 0, -1, 0, 1 \};//表示上下左右  
  
int main() \{  
    int m, n, i, j;  
    while (cin >> m >> n) \{  
        int \*\*a = new int\*\[m\];  
        for (i = 0; i < m; i++) \{  
            a\[i\] = new int\[n\];  
            for (j = 0; j < n; j++) \{  
                cin >> a\[i\]\[j\];  
            \}  
        \}  
        queue<point> q;  
        point p = \{ 0, 0 \};  
        a\[0\]\[0\] = 2;  
        q.push(p);  
        while (!q.empty()) \{  
            p = q.front();  
            q.pop();  
            for (i = 0; i < 4; i++) \{  
                point temp;  
                temp.x = p.x + list\[i\]\[0\];  
                temp.y = p.y + list\[i\]\[1\];  
                if (temp.x >= 0 && temp.x < m&&temp.y >= 0 && temp.y < n&&a\[temp.x\]\[temp.y\]==0) \{  
                    a\[temp.x\]\[temp.y\] = a\[p.x\]\[p.y\] + 1;  
                    q.push(temp);  
                \}  
            \}  
        \}  
        for (i = 0; i < m; i++) \{  
            for (j = 0; j < n; j++) \{  
                cout << left << setw(3) << a\[i\]\[j\];  
            \}  
            cout << endl;  
        \}  
  
    \}  
    return 0;  
\}