4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 0 0 0
NO YES
不过奇偶优化确实很强力。
奇偶优化的话，，，我画个图举例吧：
X是墙，其他地方是空地。从A点到B点的话，最少走2步。如果我们绕过C点的话，需要走4步，DEF点同理。每绕过一个点多走两步。
如果要求A点到B点走三步的话，就没有可行解了。
奇偶优化就是这个意思（不会数学证明……捂脸逃走）
附hdoj讨论区的数据（m，n最大为8。不加奇偶优化也能过这些数据）
4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 2 2 1 S. .D 8 8 7 .DXS...X ........ XX..XX.. .X.X.X.X ..X..... X....X.. ........ XXXX.... 5 4 18 S... .... .... .... ...D 6 6 10 S..... ...... ...... ...... ...... .....D 2 3 2 SDX ..X 2 2 3 SD .. 2 2 2 SD XX 4 4 6 .S.. XXX. XXX. XXXD 5 4 8 S... .XX. .X.. .X.X .... 3 3 3333 .S. ... ... 2 2 1 SD .. 1 5 4 S...D 4 5 5 .S... ..X.. .XDX. ..X.. 2 4 7 SD.. .... 2 2 3 S. D. 4 4 9 S..X X.X. ..XD .... 0 0 0 输出： NO YES NO NO NO YES NO YES NO NO NO NO YES YES NO YES YES YES
#include <iostream>
using namespace std;
const int dx[4]={ 1, 0,-1, 0};
const int dy[4]={ 0, 1, 0,-1};
string map[7];
int n,m,t,i,j,x1,y1,x2,y2;
int abs(int x){
return x>0?x:-x;
}
bool dfs(int x,int y,int i){
int temp=t-i-abs(x2-x)-abs(y2-y);
if (temp<0 || temp%2) return false;
for (int j=0;j<4;++j){
x+=dx[j]; y+=dy[j];
if (x>=0 && x<n && y>=0 && y<m){
if (i+1==t && map[x][y]==‘D‘) return true;
if (map[x][y]==‘.‘){
map[x][y]=‘X‘;
if (dfs(x,y,i+1)) return true;
map[x][y]=‘.‘;
}
}
x-=dx[j]; y-=dy[j];
}
return false;
}
int main()
{
while (cin>>n>>m>>t && n){
for (i=0;i<n;++i){
cin>>map[i];
for (j=0;j<m;++j)
if (map[i][j]==‘S‘){
x1=i; y1=j;
}
else if (map[i][j]==‘D‘){
x2=i; y2=j;
}
}
if (dfs(x1,y1,0)) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}kdwycz的网站： http://kdwycz.com/
kdwyz的刷题空间：http://blog.csdn.net/kdwycz
HDOJ 1010 Tempter of the Bone DFS 奇偶优化,布布扣,bubuko.com
HDOJ 1010 Tempter of the Bone DFS 奇偶优化
原文：http://blog.csdn.net/kdwycz/article/details/20145565