题目来源 蓝桥杯第十届迷宫
解答
#include
#include
using namespace std;
int eh[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
bool f[31][51];//标记某个点是否被走过
bool a[31][51];//0表示该点是路,1表示该点是墙
string ss;//存储最短路径
void dfs(int x, int y, string str)
{
if (str > ss && ss.length() != 0)//剪枝,如果当前的路径>已经存在的最小的路径,则回溯
return;
if (x == 29 && y == 49)//到达终点
{
if ((ss.length() != 0 && ss > str) || ss.length()==0)
ss = str;
return;
}
f[x][y] = 1;
for (int i = 0; i < 4; i++)
{
int n = x + eh[i][0];
int m = y + eh[i][1];
if (n>=0 && n<30 && m>=0 && m<50 && !a[n][m] && !f[n][m])
{
switch (i)
{
case 0:dfs(n, m, str + "U"); break;
case 1:dfs(n, m, str + "D"); break;
case 2:dfs(n, m, str + "L"); break;
case 3:dfs(n, m, str + "R"); break;
}
}
}
f[x][y] = 0;
}
int main()
{
for (int i = 0; i < 30; i++)
{
string temp;
cin >> temp;
for (int j = 0; j < temp.length(); j++)
a[i][j] = temp[j] - 48;
}
dfs(0, 0, "");
cout << ss << endl;
return 0;
}
错误 运行没有结果
没有结果通常三大问题:
(1)程序不优化,需要等很久
(2)程序死循环了
(3)程序没有走到输出的代码分支,就结束了,或者程序丢出异常就结束了
具体你调试下
备注:各位小可爱们如果有任何的疑问可以在评论区留下你的思考,大家一起进步 yo~