dfs经典例题——迷宫问题（利用二维数组优化方向判断）

思路首先关于方向问题我们可以设定一个默认方向比如先默认向右触底向下然后再是向左向上。只需要平行在dfs函数中即可每次递归会自动依次按照if条件进行合适方向的查找初始量地图数组注意map不要作为变量名因为有对应内置函数判断数组步数数据数组我这里采用了自增数组vector关于vectorpairint, int ans;{ans存储的单位是一个pair每个pair包含了两个数据可以利用for (auto p : ans) { cout p.first p.second ; }}然后递归判断条件需要满足step步数为最小数据数组移动到了终点位置递归过程中需要判断下一步是否是障碍物以及是否被走过。搜索过程每个方向单独列出判断代码行#includebits/stdc.h using namespace std; int themap[55][55]; // 1为空地2为障碍物 int flag[55][55]; // 0为未走过1为走过 vectorpairint, int ans; // 记录路线 int step 0; int rx, ry; int min_steps 9999; void dfs(int x, int y, int step) { if (step min_steps x rx y ry) { min_steps step; for (auto p : ans)//自动输出ans内的数据 { cout p.first p.second ; } coutstep; return; } // 右方向 if (y 1 55 themap[x][y 1] 1 flag[x][y 1] 0) { ans.push_back({x, y1});//压入此时的坐标 flag[x][y 1] 1;//标记此路已走过 dfs(x, y 1, step 1); flag[x][y 1] 0; ans.pop_back();//记得在回溯的同时弹出数组中的数据 } // 下方向 if (x 1 55 themap[x 1][y] 1 flag[x 1][y] 0) { ans.push_back({x1, y}); flag[x 1][y] 1; dfs(x 1, y, step 1); flag[x 1][y] 0; ans.pop_back(); } // 左方向 if (y - 1 0 themap[x][y - 1] 1 flag[x][y - 1] 0) { ans.push_back({x, y-1}); flag[x][y - 1] 1; dfs(x, y - 1, step 1); flag[x][y - 1] 0; ans.pop_back(); } // 上方向 if (x - 1 0 themap[x - 1][y] 1 flag[x - 1][y] 0) { ans.push_back({x-1, y}); flag[x - 1][y] 1; dfs(x - 1, y, step 1); flag[x - 1][y] 0; ans.pop_back(); } } int main() { int n, m; cin n m; cin rx ry; for (int i 0; i n; i) { for (int j 0; j m; j) { cin themap[i][j]; } } flag[0][0] 1; dfs(0, 0, 0); return 0; }优化方法由于每个方向都需要单独写出执行过程我们可以思考将四个方向合并一起达到节省代码量思路可以利用两个数组来表示x与y的方向然后每次循环从右下左上开始循环搜索路径。int tx,ty; int xd[4]{0,1,0,-1};//顺序依次是右下左上时x轴应该加减多少 int yd[4]{1,0,-1,0};//y同理 for(int i0;i3;i){ txxxd[i];//tx为下一步进入递归的坐标值为x当前值xd下一步应该加减的值 tyyyd[i]; if(themap[tx][ty]1flag[tx][ty]0) { //经过判断之后代表成功走向下一步。 ans.push_back({tx,ty});//tx,ty变成了当前值 flag[tx][ty]1; dfs(tx,ty,step1); flag[tx][ty]0; ans.pop_back(); } }完整优化代码如下#includebits/stdc.h using namespace std; int themap[55][55]; // 1为空地2为障碍物 int flag[55][55]; // 0为未走过1为走过 vectorpairint, int ans; // 记录路线 int step 0; int rx, ry; int min_steps 9999; void dfs(int x, int y, int step) { if (step min_steps x rx y ry) { min_steps step; for (auto p : ans)//自动输出ans内的数据 { cout p.first p.second ; } coutendlstep; return; } int tx,ty; int xd[4]{0,1,0,-1}; int yd[4]{1,0,-1,0}; for(int i0;i3;i){ txxxd[i]; tyyyd[i]; if(themap[tx][ty]1flag[tx][ty]0) { ans.push_back({tx,ty}); flag[tx][ty]1; dfs(tx,ty,step1); flag[tx][ty]0; ans.pop_back(); } } } int main() { int n, m; cin n m;//写入地图长和宽 cin rx ry;//写入终点坐标 for (int i 0; i n; i) { for (int j 0; j m; j) { cin themap[i][j]; } } flag[0][0] 1;//记得给起点赋值为已判断经过 dfs(0, 0, 0); return 0; }