迷宫-526互联

算法思想：将文件数据存储到邻接矩阵中，输入有效起点和终点。从起点开始深度优先搜索，如果搜索到终点则和之前存储最短路径比较，如果比它小则替换。继续搜索其他所有可能，最后输出最短路径的坐标。采用struct item来存储x和y坐标，每次DFS将当前item入栈，搜索完出栈。最后用vector存储最短路径所有的item。

主要/核心函数分析：//将起点终点反过来，方便输出路径void SearchPath(int endx, int endy, int startx,int starty)。如果当前坐标是终点，则和之前最短路径比较。如果不是中点，搜索四个方向是1的坐标。

  1 //（1）从文件中读取数据，生成模拟迷宫地图，30行30列。
  2 //（2）给出任意入口和出口，显示输出迷宫路线。
  3 #define _CRT_SECURE_NO_WARNINGS
  4 #include <iostream>
  5 #include <fstream>
  6 #include <vector>
  7 #include <stack>
  8 
  9 using namespace std;
 10 
 11 int G[33][33];//迷宫
 12 int visited[33][33] = { 0 };//标记数组
 13 int row = 1;//迷宫行数
 14 int col = 1;//迷宫列数
 15 int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };//走法
 16 
 17 typedef struct item
 18 {
 19     int x;
 20     int y;
 21     item(int mx,int my):x(mx),y(my) {}
 22 };//存储坐标信息
 23 
 24 stack<item> path;//路径
 25 vector<item>answer;//最短路径
 26 
 27 //将起点终点反过来，方便输出路径
 28 void SearchPath(int endx, int endy, int startx,int starty)
 29 {
 30     //终点
 31     if (startx == endx && starty == endy)
 32     {
 33         vector<item>temppath;
 34         while (!path.empty())
 35         {
 36             item temp = path.top();
 37             path.pop();
 38             temppath.push_back(temp);
 39         }
 40         for (int i = 0; i < temppath.size(); i++)
 41             path.push(temppath[temppath.size() - 1 - i]);
 42         if (temppath.size() < answer.size() || answer.size() == 0)
 43             answer = temppath;
 44         return;
 45     }
 46     else 
 47     {
 48         for (int i = 0; i < 4; i++)
 49         {
 50             int x = startx + dir[i][0];
 51             int y = starty + dir[i][1];
 52             if (x > 0 && x <= col && y > 0 && y <= row && visited[y][x] == 0&&G[y][x]==1)
 53             {
 54                 path.push(item(x, y));
 55                 visited[y][x] = 1;
 56                 SearchPath(endx, endy, x, y);
 57                 visited[y][x] = 0;
 58                 path.pop();
 59             }
 60         }
 61     }
 62 }
 63 
 64 int main()
 65 {
 66     FILE* fp;
 67     fp = fopen("text.txt", "r");
 68     if (!fp)
 69         return 0;
 70     while (!feof(fp))
 71     {
 72         char ch;
 73         ch=fgetc(fp);
 74 
 75         if (ch == '1' || ch == '0')
 76             G[row][col++] = ch - '0';
 77 
 78         if (ch == '\n')
 79         {
 80             row++;
 81             col = 1;
 82         }
 83     }
 84     fclose(fp);
 85     col--;
 86 
 87     cout << "该迷宫为：" << endl;
 88     for (int i = 1; i <= row; i++)
 89     {
 90         for (int j = 1; j <= col; j++)
 91             cout << G[i][j] << " ";
 92         cout << endl;
 93     }
 94 
 95     cout << "请输入起点x 起点y 终点x 终点y" << endl;
 96     int startx,starty, endx,endy;
 97     cin >> startx >>starty>> endx>>endy;
 98     while (G[starty][startx] == 0||(starty==endy&&startx==endx))
 99     {
100         cout << "起点终点有误，请重新输入" << endl;
101         cout << "请输入起点x 起点y 终点x 终点y" << endl;
102         cin >> startx >> starty >> endx >> endy;
103     }
104 
105     //将终点入栈
106     item temp1(endx, endy);
107     path.push(temp1);
108     visited[endy][endx] = 1;//标记
109 
110     SearchPath(startx,starty, endx,endy);
111 
112     cout << "最短路径为：" << endl;
113     for(int it=0;it<answer.size(); it++)
114     {
115         item temp = answer[it];
116         cout << "(" << temp.x << "," << temp.y << ")" << endl;
117     }
118 
119     return 0;
120 }

迷宫