当前位置: 代码迷 >> 综合 >> 21年寒假第一周周练/HDU1010 :Tempter of the Bone骨头的诱惑(奇偶减枝)
  详细解决方案

21年寒假第一周周练/HDU1010 :Tempter of the Bone骨头的诱惑(奇偶减枝)

热度:108   发布时间:2023-11-23 22:18:19.0

题目:

Problem Description

迷宫是一个大小为N×M的矩形。迷宫里有一扇门。一开始,门是关着的,它会在第T秒打开一小段时间(不到1秒)。因此,小狗必须正好在第T秒到达门口。在每一秒钟里,他都可以移动到上、下、左、右相邻区域。一旦他进入一个区域,这个区域的地面就会开始下沉,并在下一秒消失。他不能在一个区域停留超过一秒钟,也不能进入一个已经访问过的区域。可怜的小狗能活下来吗?请帮帮他。

Input

输入由多个测试用例组成。每个测试用例的第一行包含三个整数N、M和T(1<N、M<7;0<T<50),分别表示迷宫的大小和门打开的时间。接下来的N行给出了迷宫布局,每行包含M个字符。字符是下列字符之一:

“X”:一堵墙,小狗不能进去;

“S”:狗的起点;

“D”:门;

“.”:空区域。

Output

对于每组测试数据,如果狗能活下来输出YES,活不下来输出NO。

Sample Input
4 4 5
S.X.
…X.
…XD

3 4 5
S.X.
…X.
…D

0 0 0

Sample Output

NO
YES


解答过程分析:

确定题目类型:
迷宫问题是典型DFS的题目,用来寻找路径,这里还需要进行对时间的判断。

DFS模板框架:

function dfs(当前状态){
    if(当前状态 == 目的状态){
    ···}for(···寻找新状态){
    if(状态合法){
    vis[访问该点]dfs(新状态);?是否需要恢复现场->vis[恢复访问]} }if(找不到新状态){
    ···}
}

初步思路:
我们的目标状态为 在第T秒时可以恰好到达目标点,其中包含了两个条件:
1.可成功到达目标点
2.到达时刻恰为T
所以一开始我先确定了目标状态,写了一个初步的代码

#include<iostream>
#include<cstring>
using namespace std;
int R,C;
int h,l,x,y;
int pd;
int d;
int t;
char s;
bool f[10][10];
int ch[4]={
    -1,1,0,0},
cl[4]={
    0,0,-1,1};
void dfs(int u,int v){
    if(t==d&&u==x&&v==y){
    pd=1;}for(int i=0;i<4;i++){
    int hh=u+ch[i];int ll=v+cl[i];if(f[hh][ll]==0&&hh>=1&&hh<=R&&ll>=1&&ll<=C&&!pd){
    t++;f[hh][ll]=1;dfs(hh,ll);f[hh][ll]=0;t--;}}
}
int main(){
    while(cin>>R>>C>>d&&R&&C&&d){
    memset(f,0,sizeof(f));pd=0;t=0;for(int i=1;i<=R;i++){
    for(int j=1;j<=C;j++){
    cin>>s;if(s=='S')h=i,l=j;else if(s=='D')x=i,y=j;else if(s=='X')f[i][j]=1;}getchar();}dfs(h,l);if(pd==1) cout<<"YES"<<endl;else cout<<"NO"<<endl;}}

原因分析:

但显而易见,对于这道题来说,这么粗糙的写法,没有经过丝毫优化,只会换来超时的惨痛教训,所以我们还要进行一系列减枝优化
首先要总结哪些情况是我们需要减去的。

时间角度:
1.当时间超过了要求时,之后不论如何都是无用功。
2.当到达目标点时,时间小于目标要求(大于的情况已经被排除),之后也不必讨论。

路径角度:
我们需要引入一个奇偶减枝的方法
以大写的X,Y代表一个点的坐标,以小写的x,y代表另一个点的坐标,那么abs(X-x)+abs(Y-y)就是两点间的最小路径,记作Minlen
对于从(x,y)出发试图到达(X,Y)的任意路径,其路径记作Len
它们存在关系:
Minlen%2==Len%2,即奇偶性相同
若所给路径大小与Minlen不同,则说明该路径不可行,
而上述解答中的(t-d)就代表所给点到目标点的剩余步数,若(t-d)与Minlen连奇偶性都不同,则同样不必讨论。


解决方案:

#include<bits/stdc++.h>
using namespace std;
int R,C,d;//行,列,时间 
int h,l,x,y;//起点终点坐标 
int pd;//结果 
int t;//该状态下的时间 
char f[10][10];
int ch[4]={
    -1,1,0,0},
cl[4]={
    0,0,-1,1};
void dfs(int u,int v){
    if(t>d)return;//超时则不再可能 if ((abs(x - u) + abs(y - v)) % 2 != (d - t) % 2)return;for(int i=0;i<4;i++){
    int hh=u+ch[i];int ll=v+cl[i];if(hh==x&&ll==y&&t+1==d){
    //为了避免耗费内存,先一步判断 pd=1;return;}if(hh==x&&ll==y&&t+1!=d)continue;//可不必再继续这一步 if(f[hh][ll]!='X'&&hh>=0&&hh<R&&ll>=0&&ll<C&&pd==0){
    t++;f[hh][ll]='X';dfs(hh,ll);f[hh][ll]='.';t--;//注意恢复原来的状态 }}
}
int main(){
    while(cin>>R>>C>>d){
    if(R==0&&C==0&&d==0)break;pd=t=0;for(int i=0;i<R;i++){
    for(int j=0;j<C;j++){
    cin>>f[i][j];if(f[i][j]=='S')h=i,l=j,f[i][j]='X';else if(f[i][j]=='D')x=i,y=j;}}dfs(h,l);if(pd==1) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
}