蓝桥杯2019初赛 迷宫

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;
}