#include using namespace std; //最小步数 int _min = INT_MAX; //行数 const int n = 5; //列数 const int m = 4; //小哈位置x坐标+y坐标 const int p = 2; const int q = 3; //地图 int a[n][m]; //标记数组,哪个走过了? int book[n][m]; /** * 功能:深度优先搜索走迷宫 * 作者:黄海 * 时间:2019-11-17 * @param x * @param y * @param step */ void dfs(int x, int y, int step) { int next[4][2] = { {0, 1},//向右走 {1, 0},//向下走 {0, -1},//向左走 {-1, 0},//向上走 }; int tx, ty, k; if (x == p && y == q) //判断是否到达小哈的位置 { if (step < _min) _min = step; //更新最小值 return; } /*枚举四种走法*/ for (k = 0; k <= 3; k++) { /*计算下一个点的坐标*/ tx = x + next[k][0]; ty = y + next[k][1]; if (tx < 0 || tx > n - 1 || ty < 0 || ty > m - 1) //判断是否越界 continue; /*判断该点是否为障碍物或者已经在路径中*/ if (a[tx][ty] == 0 && book[tx][ty] == 0) { book[tx][ty] = 1; //标记这个点已经走过 dfs(tx, ty, step + 1); //开始尝试下一个点 book[tx][ty] = 0; //尝试结束,取消这个点的标记 } } return; } int main() { //起点和终点坐标 int startx = 0; int starty = 0; //从文件中读取地图数据 string file = "../data.in"; //fstream 流方法读数据 ifstream fin(file); //读取地图 for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) fin >> a[i][j]; //关闭文件 fin.close(); fin.clear(ios::goodbit); /*从起点开始搜索*/ book[startx][starty] = 1; //标记起点已经在路径中,防止后面重复走 dfs(startx, starty, 0); //第一个参数是起点的x坐标,以此类推是起点的y坐标,初始步数为0 printf("%d", _min); //输出最短步数 return 0; }