• 欢迎光临~

HDU 1010 Tempter of the Bone(DFS 剪枝)

开发技术 开发技术 2022-12-28 次浏览

HDU 1010 Tempter of the Bone

题意

​ 有一个(n times m)的地图,上面有若干障碍物,给定起点和终点,还有步数 k 。你当前在起点,请问你是否能恰好在第 k 步的时候走到终点。

思路

​ 简单爆搜,需要一点小小的剪枝。比较特殊的是,他的数据组数有点多,可以知道,若问题无解,需要把整个图搜一遍,这样会很慢,所以在开头先特判一些明显无解的情况,可以减少很多运行时间。

实现

#include <bits/stdc++.h>
    
using namespace std;
const int N = 10;

int n, m, k;
char g[N][N];
int vis[N][N];
int ok;
int sx, sy, ex, ey;
int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, - 1}};
#define CHECK(x, y) (x >= 1 && x <= n && y >= 1 && y <= m)

void dfs(int x, int y, int step)
{
    if(ok) 
        return;
    if(g[x][y] == 'D')
    {
        if(step == k)
            ok = 1;
        return;
    }
    if(step + abs(x - ex) + abs(y - ey) > k) //可行性剪枝,如果当前加上最短距离之后步数大于k的话,显然是无效的
        return;
    for(int i = 0; i < 4; i ++)
    {
        int xx = x + d[i][0], yy = y + d[i][1];
        if(CHECK(xx, yy) && !vis[xx][yy] && g[xx][yy] != 'X')
        {
            vis[xx][yy] = 1;
            dfs(xx, yy, step + 1);
            vis[xx][yy] = 0; //回溯
        }
    }
    return;
}

void init()
{
    memset(vis, 0, sizeof vis);
    ok = 0;
}

int main()
{
    while(scanf("%d%d%d", &n, &m, &k))
    {
        if(!n && !m && !k)
            break;
        for(int i = 1; i <= n; i ++)
            scanf("%s", g[i] + 1);

        for(int i = 1; i <= n; i ++)
            for(int j = 1; j <= m; j ++)
            {
                if(g[i][j] == 'S')
                    sx = i, sy = j;
                if(g[i][j] == 'D')
                    ex = i, ey = j;
            }
        int dis = abs(sx - ex) + abs(sy - ey);
        int step = k - dis;
        if(step < 0 || dis % 2 != k % 2) //无解要搜索整个图,时间复杂度很高。
        {
            //关于曼哈顿距离和最短步数奇偶性必然相同这一点,可以画图理解一下
            cout << "NOn";
            continue;
        }
        init();
        vis[sx][sy] = 1; //一定要记得把起点标记。
        dfs(sx, sy, 0);
        if(ok)
            cout << "YESn";
        else
            cout << "NOn";
    }
}
程序员灯塔
转载请注明原文链接:HDU 1010 Tempter of the Bone(DFS 剪枝)
喜欢 (0)