代码: 参考资料
摘要: 难度
第2行: 第2行:
 
[[分类:深度优先搜索]][[分类:广度优先搜索]]
 
[[分类:深度优先搜索]][[分类:广度优先搜索]]
 
==摘要==
 
==摘要==
{{信息题|Tempter of the Bone|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}68572#problem/K|1|100|time=2015-02-06 14:43:00}}
+
{{信息题|Tempter of the Bone|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}68572#problem/K|2|100|time=2015-02-06 14:43:00}}
 
*来自寒假练习:[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=68572 Only a signing tool !] K题
 
*来自寒假练习:[http://acm.hust.edu.cn/vjudge/contest/view.action?cid=68572 Only a signing tool !] K题
 
*原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1010
 
*原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=1010
 +
 
==题意==
 
==题意==
 
在n*m的地图上求从S走到D是否能够恰好t步走完。
 
在n*m的地图上求从S走到D是否能够恰好t步走完。

2015年2月7日 (六) 14:11的版本

摘要

题目链接 难度等级 完成状态 完成分数 最后编辑时间 需要注意
Tempter of the Bone ★★☆☆☆ 答案正确 100 2015-02-06 14:43:00

题意

在n*m的地图上求从S走到D是否能够恰好t步走完。

题解

显然还是搜索题,裸搜会T,所以要剪枝,加上下面两个剪枝好像就Acceptable了:

奇偶性剪枝

这是不太好想的,我的确用了百度优先搜索[1]……限制语句是这样的

((ex+sx+ey+sy+t)%2)//(ex,ey)为终点,(sx,sy)为起点//

想到这样一个矩阵就比较好理解,x+y为偶数时 为0 否则为1:

   0    1    0    1    0
   1    0    1    0    1
   0    1    0    1    0
   1    0    1    0    1

由图可知,任意一个点相邻的必然是与本身相反的值,也就是说,要想走到与本身值相同的点必然要走偶数步,同理,要想走到与本身相异的值的点必然要走奇数步; 所以,当两个位置的x+y奇偶性相同时(同为0或同为1)若时间为奇数 则必然无法到达;当两个位置的奇偶性不同时(一个为1,另一个为0)若时间为偶数也必不能到达,可以被剪枝。

可行性剪枝

代码如下

(abs(sx-ex)+abs(sy-ey)>t)||(n*m-w<t)//w代表墙的个数//
意思是:
  1. 如果直接无视障碍走过去的时间都不只t,那么直接剪枝。
  2. 如果去掉墙所有的位置都走一遍的时间还少于t,那么也直接剪枝。

代码

1010.cpp代码已折叠
展开折叠内容
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#define ci const int &
using namespace std;
const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
bool visited[10][10]={};
char a[10][10]={};
int n,m,t,sx,sy,ex,ey,w=0;
const bool dfs(ci x,ci y,ci t)
{
    if(!t&&a[x][y]=='D')
        return 1;
    if(!t)return 0;
    if(visited[x][y]||a[x][y]!='.')
        return 0;
    visited[x][y]=1;
    for(int i=0;i<4;++i)
    {
        if(dfs(x+dx[i],y+dy[i],t-1))
        {
            visited[x][y]=0;
            return 1;
        }
    }
    visited[x][y]=0;
    return 0;
}
int main()
{
    while(1)
    {
        cin>>n>>m>>t;
        if(!n)
            return 0;
        w=1;
        for(int i=1;i<=n;++i)
        {
            for(int j=1;j<=m;++j)
            {
                cin>>a[i][j];
                if(a[i][j]=='S')
                    sx=i,sy=j,a[i][j]='.';
                if(a[i][j]=='D')
                    ex=i,ey=j;
                if(a[i][j]=='X')
                    ++w;
            }
        }
        if(((ex+sx+ey+sy+t)&1)||(abs(sx-ex)+abs(sy-ey)>t)||(n*m-w<t))//奇偶性剪枝,可行性剪枝//
            cout<<"NO\n";
        else if(dfs(sx,sy,t))
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
}


参考资料和拓展阅读

  1. http://blog.csdn.net/cyg0810/article/details/8194108

著作权声明[编辑]

关于[编辑]