HDU_(1010) Tempter of the Bone(DFS,剪枝)

题目请点我

题意:

有一个迷宫,看能不能经过T秒恰好从起点走到终点。因为可能会考虑到绕路,2^49可能会超时(况且涉及到绕路,墙的数目一定不会很多),我们就可以在每次都进行一次判断,看剩下的时间能否走到终点。另外因为只能在T秒走到,那么绕路的话一定会多走偶数步数,利用这个性质也可以剪枝。这道题其实之前做过的,但是第二次做还是TLE了很多次,其实这题的关键不仅是dfs,在T秒恰好到达需要绕路才是这道题的亮点,trap也在这里。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAX 10
#define INF 100

using namespace std;

int N,M,T;
bool flag;
int sx,sy,ex,ey;
int dx[4] = {0,-1,0,1};
int dy[4] = {1,0,-1,0};
char maze[MAX][MAX];
void dfs(int x,int y,int time);
int main()
{
    while( scanf("%d%d%d",&N,&M,&T) != EOF ){
        if( N == 0 && M == 0 && T == 0 ){
            break;
        }
        flag = false;
        getchar();
        for( int i = 0; i < N; i++ ){
            for( int j = 0; j < M; j++ ){
                scanf("%c",&maze[i][j]);
                if( maze[i][j] == ‘S‘ ){
                    sx = i;
                    sy = j;
                }
                else if( maze[i][j] == ‘D‘ ){
                    ex = i;
                    ey = j;
                }
            }
            getchar();
        }
        maze[sx][sy] = ‘X‘;
        dfs(sx,sy,0);
        if( flag ){
            printf("YES\n");
        }else{
            printf("NO\n");
        }
    }
    return 0;
}

void dfs( int x, int y,int time){
    if( x == ex && y == ey ){
        if( time == T ){
            flag = true;
        }
        return ;
    }
    int left = T-time-abs(x-ex)-abs(y-ey);
    if( left<0 || left%2 == 1 ){
        return ;
    }
    for( int i = 0; i < 4; i++ ){
        int nx = x+dx[i];
        int ny = y+dy[i];
        if( nx >= 0 && nx < N && ny >= 0 && ny < M && maze[nx][ny] != ‘X‘ && !flag ){
            char tmp = maze[nx][ny];
            maze[nx][ny] = ‘X‘;
            dfs(nx,ny,time+1);
            maze[nx][ny] = tmp;
        }
    }
}
时间: 06-13

HDU_(1010) Tempter of the Bone(DFS,剪枝)的相关文章

HDU 1010 Tempter of the Bone dfs+剪枝

给你一个迷宫一个起点和一个终点,问你能否走T步刚好到达终点,不能重复走,并且只有4个方向 显然这是一个dfs,虽然N最大只有7,但是裸的dfs复杂度还是太高了,因此要进行一些剪枝 1.如果T比图上所有的可走点还要大,肯定是不可行的.这个可以避免dfs整张图. 2.奇偶剪枝,有性质当前点(x,y)到目标点(tx,ty)的所有路径的长度的奇偶性一定和|x-tx|+|y-ty|一样. #include <cstdio> #include <iostream> #include <c

HDU 1010 Tempter of the Bone(DFS剪枝)

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 129289    Accepted Submission(s): 34906 Problem Description The doggie found a bone in an ancient maze, which fascinated him a

HDU 1010 Tempter of the Bone heuristic 剪枝法

本题就是考剪枝法了. 应该说是比较高级的应用了.因为要使用heuristic(经验)剪枝法.要总结出这个经验规律来,不容易.我说这是高级的应用也因为网上太多解题报告都没有分析好这题,给出的程序也很慢,仅仅能过掉,由此看来很多人没有做好这道题. 这里我需要更正一下网上流行的说法:奇偶剪枝法. 其实本题使用奇偶剪枝法并不能太大提高速度,只能说仅仅让使用奇偶剪枝过掉.所以网上说本题使用奇偶剪枝的,其实并不能提高速度. 原因: 奇偶剪枝只能剪枝一次,不能在递归的时候剪枝,因为只要初始化位置符合奇偶性,那

HDU 1010 Tempter of the Bone (DFS 奇偶剪枝)

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 75141    Accepted Submission(s): 20531 Problem Description The doggie found a bone in an ancient maze, which fascinated him a

hdu.1010.Tempter of the Bone(dfs+奇偶剪枝)

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 82702    Accepted Submission(s): 22531 Problem Description The doggie found a bone in an ancient maze, which fascinated him a

hdu 1010 Tempter of the Bone DFS+奇偶剪枝,入门题

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 78390    Accepted Submission(s): 21395 Problem Description The doggie found a bone in an ancient maze, which fascinated him a

hdu1010 Tempter of the Bone(DFS+剪枝)

Tempter of the Bone Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 90716    Accepted Submission(s): 24683 Problem Description The doggie found a bone in an ancient maze, which fascinated him a

hdu - 1010 Tempter of the Bone (dfs+奇偶性剪枝) &amp;&amp; hdu-1015 Safecracker(简单搜索)

http://acm.hdu.edu.cn/showproblem.php?pid=1010 这题就是问能不能在t时刻走到门口,不能用bfs的原因大概是可能不一定是最短路路径吧. 但是这题要过除了细心外,还需要强力的剪枝. 奇偶性剪枝:参考 http://www.cppblog.com/Geek/archive/2010/04/26/113615.html 1 #include <iostream> 2 #include <cstring> 3 #include <cstdi

HDU 1010 Tempter of the Bone DFS 简单题 注意剪枝

题意:一只小狗要刚好在t时刻从起点都到终点,问可不可以. 注意剪枝. 1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 using namespace std; 5 int maze[9][9]; 6 bool vis[9][9]; 7 int n,m,t; 8 bool ans; 9 struct Point 10 { 11 int x,y; 12 }; 13 int dx[4]={0,0,-1,1}