小 （→代码： 参考资料） |
小 （→摘要： 难度） |
||
| 第2行： | 第2行： | ||
[[分类:深度优先搜索]][[分类:广度优先搜索]] | [[分类:深度优先搜索]][[分类:广度优先搜索]] | ||
==摘要== | ==摘要== | ||
| − | {{信息题|Tempter of the Bone|http://acm.hust.edu.cn/vjudge/contest/view.action?cid{{=}}68572#problem/K| | + | {{信息题|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步走完。 | ||
| 题目链接 | 难度等级 | 完成状态 | 完成分数 | 最后编辑时间 | 需要注意 |
|---|---|---|---|---|---|
| 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代表墙的个数// 意思是：
| 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";
}
}
|
CloudLunar