url: http://oj.ecustacm.cn/problem.php?id=1455
tag: 搜索
思路:使用bfs或者dfs。如果使用bfs需要将每次的路径也放入队列中,当搜到终点时,就直接将答案输出。使用dfs需要使用一种记忆化的剪枝技巧,每次判断当前的路径长度 + 1和即将到达的那个点的到那个点的最短的长度比较,如果大于就直接跳过,如果小于就更新那个点的值。这种做法含有记忆化搜索的思想。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char d[31][51];
char r[] = {'D', 'U', 'L', 'R'};
int nx[] = {1, -1, 0, 0};
int ny[] = {0, 0, -1, 1};
int minv = 0x3f3f3f3f;
string res = "";
bool st[31][51];
int mastep[31][51];
void dfs(int len, int x, int y, string ans)
{
if (x == 30 && y == 50)
{
if (len == minv)
{
res = min(res, ans);
}
if (len < minv)
{
minv = len;
res = ans;
}
return;
}
for (int i = 0; i < 4; i ++)
{
int xx = x + nx[i], yy = y + ny[i];
if (xx < 1 || xx > 30 || yy < 1 || yy > 50 || st[xx][yy] || d[xx][yy] == '1') continue;
if (len + 1 > mastep[xx][yy]) continue;
if (len >= minv) continue;
st[xx][yy] = true;
mastep[xx][yy] = len + 1;
dfs(len + 1, xx, yy, ans + r[i]);
st[xx][yy] = false;
}
}
int main()
{
memset(mastep, 0x3f, sizeof mastep);
for (int i = 1; i <= 30; i ++)
for (int j = 1; j <= 50; j ++)
cin >> d[i][j];
dfs(0, 1, 1, "");
cout << res << endl;
return 0;
}
答案:
#include <iostream>
using namespace std;
int main()
{
cout << "DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR" << endl;
}