题目描述 给定n*m的迷宫 (2<n,m<24) ,迷宫中’0’代表路,'1’代表墙,'2’代表起点,'3’代表终点,求起点到终点最短距离
输入 多实例测试 第一行输入n,m 下面是n行,每行输入m个字符 输出 输出起点到终点最短距离 样例输入 5 3 0 0 0 0 1 0 0 2 0 0 1 3 0 0 0 样例输出 2 提示 多组样例输入
思路：使用的是深搜dfs
#include <iostream> #include <algorithm> using namespace std; int map[30][30], vis[30][30], step = 0, minn = 100000, n, m; int a[][2] = {1, 0, 0, 1, -1, 0, 0, -1};//控制行进方向 void dfs(int x, int y, int step) { if(map[x][y] == 3)//寻求最短路 { if(step < minn) minn = step; return; } for(int i = 0; i < 4; i++) { x += a[i][0];//控制方向，能走就继续沿着这个方向走 y += a[i][1]; if(x >= 0 && y >= 0 && x < n && y < m && map[x][y] != 1 && vis[x][y] != 1)//找路，看是否可以走 { step++; vis[x][y] = 1;//走过的路标记为1 dfs(x, y, step);//返回，步数-，地图标记为0 step--; vis[x][y] = 0; } x -= a[i][0];//控制方向，能走就继续沿着这个方向走 y -= a[i][1]; } } int main() { int x, y; cin >> n >> m; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { cin >> map[i][j]; if(map[i][j] == 2) x = i, y = j;//记录起始坐标 } } dfs(x, y, 0); cout << minn << endl; return 0; }