Sample Output
NO
YES
我们定义剩余时间为 res ，如果剩余时间很多且 res 为奇数那么必然不可能恰好到达，因为每多拐一个弯则必然多出偶数步，所以 res 与 距离终点的格子数应该具有相同的奇偶性。
#pragma GCC optimize(2)
#include <bits/stdc++.h>
/*#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>*/
#define rush() int T;cin>>T;while(T--)
#define ms(a,b) memset(a,b,sizeof a)
#define E 1e-11
#define sd(a) scanf("%d",&a)
#define sdd(a,b) scanf("%d%d",&a,&b)
#define sf(a) scanf("%lf",&a)
#define sc(a) scanf("%c\n",&a)
#define ss(a) scanf("%s",&a)
#define pd(a) printf("%d\n",a)
#define pdd(a,b) printf("%d %d\n",a,b)
#define pddd(a,b,c) printf("%d %d %d\n",a,b,c)
#define pld(a) printf("%I64d\n",a)
#define pf(a) printf("%.2lf\n",a)
#define REP(a) for(int i=0;i<(a);i++)
#define debug(a) cout<<"*"<<a<<"*"<<endl
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define PAUSE system("pause")
#define fr first
#define sc second
using namespace std;
typedef long long ll;
//using ui=unsigned int;
typedef unsigned long long ull;
typedef pair<int,int> Pair;
const double pi=acos(-1.0);
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const int inf=0x7f7f7f7f;
const int mod=1e9+7;
const int N=10+5;
int n,m,t;
int i,j,k;
char a[N][N];
bool flag;
bool valid(int x,int y)
{
if(x<0 || x>=n) return false;
if(y<0 || y>=m) return false;
return true;
}
void dfs(int x,int y,int cost,int aimx,int aimy)
{
if(flag) return ;
if(!cost)
{
if(x==aimx&&y==aimy)
flag=1;
return ;
}
if( cost<abs(x-aimx)+abs(y-aimy) ) return ;
if( ( cost-abs(x-aimx)-abs(y-aimy) )&1 ) return ;//奇偶剪枝
for(int i=0;i<4;i++)
{
int nx=x+dx[i],ny=y+dy[i];
if(valid(nx,ny)&&(a[nx][ny]=='.'||a[nx][ny]=='D'))
{
a[nx][ny]='X';
dfs(nx,ny,cost-1,aimx,aimy);
a[nx][ny]='.';
}
}
return ;
}
int main()
{
while(scanf("%d%d%d",&n,&m,&t),m)
{
int x,y,nx,ny;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
cin>>a[i][j];
if(a[i][j]=='S')
nx=i,ny=j;
if(a[i][j]=='D')
x=i,y=j;
}
flag=0;
dfs(nx,ny,t,x,y);
puts(flag ? "YES" : "NO");
}
return 0;
}
