題目原文：http://acm.hdu.edu.cn/showproblem.php?pid=1010
題目大意：給出起始位置和終點(diǎn)位置，要求在指定的時(shí)間剛好到達(dá)終點(diǎn)時(shí)間，每移動(dòng)一步一秒，并且不能返回。
題目分析：
1。起初以為能用BFS做，后來(lái)發(fā)現(xiàn)，必須在指定的時(shí)間內(nèi)抵達(dá)終點(diǎn)才行，BFS無(wú)法達(dá)到要求。
2。要求在指定時(shí)間內(nèi)到達(dá)，唯一想法就是能不能枚舉出所有抵達(dá)方案，再在通過(guò)檢查時(shí)間時(shí)間是否吻合，得到結(jié)果，這就自然想到了用DFS進(jìn)行搜索。
3。DFS搜索完成后，提交發(fā)現(xiàn)超時(shí)，看樣子還得剪枝才行，無(wú)奈啊，百度一下。
4。剪枝方法：奇偶剪枝
把map看作
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
從 0->1 需要奇數(shù)步
從 0->0 需要偶數(shù)步
那么設(shè)所在位置 (x,y) 與 目標(biāo)位置 (dx,dy)
如果abs(x-y)+abs(dx-dy)為偶數(shù)，則說(shuō)明 abs(x-y) 和 abs(dx-dy)的奇偶性相同，需要走偶數(shù)步
如果abs(x-y)+abs(dx-dy)為奇數(shù)，那么說(shuō)明 abs(x-y) 和 abs(dx-dy)的奇偶性不同，需要走奇數(shù)步
理解為 abs(si-sj)+abs(di-dj) 的奇偶性就確定了所需要的步數(shù)的奇偶性?。?/p>
而 (ti-setp)表示剩下還需要走的步數(shù)，由于題目要求要在 ti時(shí) 恰好到達(dá)，那么 (ti-step) 與 abs(x-y)+abs(dx-dy) 的奇偶性必須相同
因此 temp=ti-step-abs(dx-x)-abs(dy-y) 必然為偶數(shù)！
5。最后一點(diǎn)：整個(gè)圖的可以移動(dòng)步數(shù)應(yīng)該大于指定的時(shí)間
#include "iostream"
#include <math.h>
using namespace std;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
int n,m;
char a[7][7];
int sx,sy,dx,dy;
int ti,flag;
void DfsSerch(int x,int y,int step)
{
/////////////////////////////////////
int temp;
temp=ti-step-abs(dx-x)-abs(dy-y);
if (temp<0||temp%2==1) return;
////////////////////////////////////
int tx,ty;
for(int i=0;i<4;i++) //方向探索
{
tx=x+dir[i][0];
ty=y+dir[i][1];
if (a[tx][ty]=='D'&&step==ti-1)
{
flag=1;
return ;
}
if(a[tx][ty]=='.'&&(tx>=0&&tx<n)
&&(ty>=0&&ty<m))
{
a[tx][ty]='X'; //標(biāo)記訪(fǎng)問(wèn)
DfsSerch(tx,ty,step+1);
a[tx][ty]='.'; //回溯取消標(biāo)記
if(flag==1) return;//找到直接返回
}
}
}
int main()
{
while (cin>>n>>m>>ti&&n!=0||m!=0||ti!=0)
{
///////////////////////////////////////
//輸入數(shù)據(jù)
int wall=0;
for (int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S')
{
sx=i;
sy=j;
}
if (a[i][j]=='D')
{
dx=i;
dy=j;
}
if (a[i][j]=='X')
{
wall++;
}
}//for-for
/////////////////////////////////////
flag=0;
if (n*m-wall<=ti)
{
cout<<"NO"<<endl;
continue;
}
DfsSerch(sx,sy,0);
if(flag==1)
cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}