前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >DFS练习-HDU1010

DFS练习-HDU1010

作者头像
Enterprise_
发布2019-02-21 17:13:02
5790
发布2019-02-21 17:13:02
举报
文章被收录于专栏:小L的魔法馆

题目来源:HDU1010 DFS的基本原则已经差不多了,但是一些技巧仍然比较难想,所以还是加强练习,然后总结一下。

还是先看题意 ,指定迷宫的长,宽以及走出迷宫的具体时间N,M,T。 其中(1 < N, M < 7; 0 < T < 50)。 在这个迷宫中,从起点 ‘S’ 出发,每经过一个格子就花费一秒,不可掉头。 而要做的就是判断是否有一条从起点到终点 ‘D’ 的路恰好花费T秒。 如果有就输出YES,否则就是NO了。

再看代码:

代码语言:javascript
复制
#include<stdio.h>
#include<math.h>
char maze[10][10];      //迷宫
int flag;           //YES OR NO
int N, M, T;        //迷宫的长和宽,和限定的时间
int dirction[4][2] =
{
    { 0,1 },{ 1,0 },
    { 0,-1 },{ -1,0 }
};                          //四个遍历方向
int sx, sy;         //起点坐标
int gx, gy;         //终点坐标
void dfs(int x, int y, int time)
{
    if (flag)
        return;     //条件符合
    if (x == gx&&y == gy&&time == T)
    {
        flag = 1;
        return;
    }
    if (abs(x - gx) + abs(y - gy) > T - time || (x + gx + y + gy + T - time) % 2 == 1)
        return;
    if (time > T)
        return;
    for (int i = 0; i < 4; i++)
    {
        int dx = x + dirction[i][0];
        int dy = y + dirction[i][1];
        if (dx < N&&dx >= 0 && dy >= 0 && dy < M&&maze[dx][dy] != 'X')
        {
            maze[dx][dy] = 'X';
            dfs(dx, dy, time + 1);
            maze[dx][dy] = '.';
        }
    }
}

int main(void)
{
    while (scanf("%d %d %d", &N, &M, &T) != EOF)
    {
        if ((N + M + T) == 0)
            break;
        int i, j;
            for (i = 0; i < N; i++)
            {
                getchar();
                for (j = 0; j < M; j++)
                {
                    scanf("%c", &maze[i][j]);
                    if (maze[i][j] == 'S')
                    {
                        sx = i;
                        sy = j;
                    }
                    if (maze[i][j] == 'D')
                    {
                        gx = i;
                        gy = j;
                    }
                }
            }
        getchar();
        maze[sx][sy] = 'X';
        flag = 0;
        dfs(sx, sy, 0);
        if (flag == 1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

1.main函数

代码语言:javascript
复制
int main(void)
{
    while (scanf("%d %d %d", &N, &M, &T) != EOF)
    {
        if ((N + M + T) == 0)
            break;
        int i, j;
            for (i = 0; i < N; i++)
            {
                getchar();
                for (j = 0; j < M; j++)
                {
                    scanf("%c", &maze[i][j]);
                    if (maze[i][j] == 'S')
                    {
                        sx = i;
                        sy = j;
                    }
                    if (maze[i][j] == 'D')
                    {
                        gx = i;
                        gy = j;
                    }
                }
            }
        getchar();
        maze[sx][sy] = 'X';
        flag = 0;
        dfs(sx, sy, 0);
        if (flag == 1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

按照题意,输入三个数,迷宫的长宽,以及规定时间,N,M,T。 第一个if控制主循环退出,即0 0 0退出 。 接着用循环记录迷宫,顺便记录下起点和终点的坐标值。 设置判断成功与否的标志的flag为0,就开始DFS了。

2.dfs函数

代码语言:javascript
复制
void dfs(int x, int y, int time)
{
    if (flag)
        return;     //条件符合
    if (x == gx&&y == gy&&time == T)
    {
        flag = 1;
        return;
    }
    if (abs(x - gx) + abs(y - gy) > T - time || (x + gx + y + gy + T - time) % 2 == 1)
        return;      //剪枝2
    if (time > T)
        return;      //剪枝1
    for (int i = 0; i < 4; i++)
    {
        int dx = x + dirction[i][0];
        int dy = y + dirction[i][1];
        if (dx < N&&dx >= 0 && dy >= 0 && dy < M&&maze[dx][dy] != 'X')
        {
            maze[dx][dy] = 'X';
            dfs(dx, dy, time + 1);
            maze[dx][dy] = '.';
        }
    }
}

第一个if判断是否找到符合题意的解,有就退出,不再搜索。 第二个如果在规定的时间内到达了终点的话,就设置flag=1,即存在这样的解

代码语言:javascript
复制
    if (flag)
        return;     //条件符合
    if (x == gx&&y == gy&&time == T)
    {
        flag = 1;
        return;
    }

循环主体部分:

代码语言:javascript
复制
 for (int i = 0; i < 4; i++)
    {
        int dx = x + dirction[i][0];
        int dy = y + dirction[i][1];
        if (dx < N&&dx >= 0 && dy >= 0 && dy < M&&maze[dx][dy] != 'X')
        {
            maze[dx][dy] = 'X';
            dfs(dx, dy, time + 1);
            maze[dx][dy] = '.';
        }
    }

四个方向的遍历,如果这个点的坐标满足要求,即在迷宫之内并且迷宫中这个点不是墙。 DFS中已经搜索过的点不能重复搜索,所以需要先将这个点设置为墙,然后dfs,再复原,进行回溯的操作。

代码语言:javascript
复制
maze[dx][dy] = 'X';
dfs(dx, dy, time + 1);
maze[dx][dy] = '.';

剪枝问题 注释上的剪枝1

代码语言:javascript
复制
    if (time > T)
        return;      //剪枝1

当消耗的时间超过了题目规定的时间,说明已经不存在符合题意的解,那应该不需要再往下搜索了。 如果不包含剪枝2,直接提交也没办法通过,因为会超时 QAQ。 注释上的剪枝2

代码语言:javascript
复制
if (abs(x - gx) + abs(y - gy) > T - time || (x + gx + y + gy + T - time) % 2 == 1)
        return;      //剪枝2

这个剪枝包含了01剪枝,也叫做奇偶剪枝

2.1奇偶剪枝

这就是技巧,弄清除原理,就好理解了QWQ。 先给出一个6X6的数组: 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 好像没什么意义……好吧,主要是看步数。 从0开始走,走1步会走到1;从1开始走,走1步会走到0. 从0开始走,走2步会走到0;从1开始走,走2步会走到1. 从0开始走,走3步会走到1;从1开始走,走3步会走到0. 从0开始走,走4步会走到0;从1开始走,走4步会走到1. 从0开始走,走5步会走到1;从1开始走,走5步会走到0. 从0开始走,走6步会走到0;从1开始走,走6步会走到1. …… 找找规律,0走偶数步到0,1同理;0走奇数步到1,1走奇数步到0 但是这个和这道题有什么关系? 所以先做一个假设,题目给出如上数组,这个数组上都是可以通过的,即都是 ‘.’ 起点是(1,1),终点是(5,5)。 这个时候走9步就可以到达终点了。 那么T如果给的是13,能否在时间内恰好到达? 不能。

换一组数据,起点是(0,4),终点是(4,3),T=6,能否成功? 看下上面的数组,(0,4)是0,(4,3)是1,T是偶数,所以不能到达。 但是看数组并不好,一般这样来判断是0还是1: (0,4)是(0+4)%2=0 (4,3)是(4+3)%2=1

那么将(0,4)和(4,3)这一组数据中的T换成7,7是奇数,是否能说明一定成功? 很明显不能,如果这样就能判断的话,还要dfs干嘛?! (O_O) 在刚才的假设中,实际只需要5步就可以到达终点,所以T=7仍然不符合题意。 所以,还需要一个判断,实际距离和剩余时间的比较距离:abs(sx-gx)+abs(sy-gy),在只能直走的情况下,这就是最短的距离了。 所以abs(sx-gx)+abs(sy-gy) < Time ,就能到达了吗? 不一定。因为这样的话,才有可能到达。 如果abs(sx-gx)+abs(sy-gy) > Time 会发生什么? 说明在没有墙的情况下,那只小狗沿着最短的路都不可能到达终点,那么一定是无解的了。 最后综合一下的条件: abs(sx-gx)+abs(sy-gy) > Time (Time是剩余时间) 奇偶性: (x+y)%2与(gx+gy)%2与Time%2 (gx,gy是终点坐标,x,y是当前点的坐标,Time是剩余时间) 可以和起来判断: (x + gx + y + gy + Time ) % 2 != 0 以上条件都不可能到达。 这就是剪枝2的内容。

那么结果是怎么样的呢?

这里写图片描述
这里写图片描述

第一行就是一开始的代码结果,虽然过了,但是时间上感觉不是太好。 所以有了第二行以及第三行。

剪枝3

这个我没有想到,通过别人的代码得知。

通过迷宫可以得知墙体的数目,这就可以算出‘.’的数目了,即N*M-sum. sum是墙体的数目. 这代表这只小狗在迷宫内最多只能待这么长的时间。 如果这个时间比规定的时间T还要小,小狗根本不能存活了。 所以,N*M-sum>T

最后的代码

代码语言:javascript
复制
#include<stdio.h>
#include<math.h>
char maze[10][10];      //迷宫
int flag;           //YES OR NO
int N, M, T;        //迷宫的长和宽,和限定的时间
int dirction[4][2] =
{
    { 0,1 },{ 1,0 },
    { 0,-1 },{ -1,0 }
};                          //四个遍历方向
int sx, sy;         //起点坐标
int gx, gy;         //终点坐标
void dfs(int x, int y, int time)
{
    if (flag)
        return;     //条件符合
    if (x == gx&&y == gy&&time == T)
    {
        flag = 1;
        return;
    }
    if (abs(x - gx) + abs(y - gy) > T - time || (x + gx + y + gy + T - time) % 2 == 1)
        return;
    if (time > T)
        return;
    for (int i = 0; i < 4; i++)
    {
        int dx = x + dirction[i][0];
        int dy = y + dirction[i][1];
        if (dx < N&&dx >= 0 && dy >= 0 && dy < M&&maze[dx][dy] != 'X')
        {
            maze[dx][dy] = 'X';
            dfs(dx, dy, time + 1);
            maze[dx][dy] = '.';
        }
    }
}

int main(void)
{
    while (scanf("%d %d %d", &N, &M, &T) != EOF)
    {
        if ((N+M+T)==0)
            break;
        int i, j, sum=0;
        for (i = 0; i < N; i++)
        {
            getchar();
            for (j = 0; j < M; j++)
            {
                scanf("%c", &maze[i][j]);
                if (maze[i][j] == 'S')
                {
                    sx = i;
                    sy = j;
                }
                if (maze[i][j] == 'D')
                {
                    gx = i;
                    gy = j;
                }
                if (maze[i][j] == 'X')  
                    sum++;
            }
        }
        getchar();
        if (N*M - sum <= T)
        {
            printf("NO\n");
            continue;
        }
        maze[sx][sy]='X';
        flag = 0;
        dfs(sx, sy, 0);
        if (flag==1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

至于第三个C++的代码,没有什么太大的改进,只是改写,就不帖出来了。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017年08月16日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 再看代码:
  • 1.main函数
  • 2.dfs函数
  • 2.1奇偶剪枝
  • 剪枝3
  • 最后的代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档