hdu1010

发表于 | 分类于 | 阅读数 次

链接:hdu1010

题解

  • 简单dfs+奇偶剪枝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=20;
pair<int,int> S,D;
char mp[N][N];
int vis[N][N],n,m,T;
int dx[5]={0,-1,1,0,0};
int dy[5]={0,0,0,-1,1};
inline int dis(int x,int y){return abs(x-D.first)+abs(y-D.second);}
int dfs(int x,int y,int c){
	if(c==T&&mp[x][y]=='D')return 1;
	int t=T-dis(x,y)-c;s
	if(c>=T||t<0||t&1)return 0;
	rep(i,1,4){
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m||mp[nx][ny]=='X'||vis[nx][ny])continue;
		vis[nx][ny]=1;
		if(dfs(nx,ny,c+1))return 1;
		vis[nx][ny]=0;
	}
	return 0;
}
int main(){
	while(~scanf("%d%d%d",&n,&m,&T)&&n){
		memset(vis,0,sizeof vis);
		rep(i,1,n)scanf("%s",mp[i]+1);
		rep(i,1,n)rep(j,1,m){
			if(mp[i][j]=='S')S=make_pair(i,j);
			if(mp[i][j]=='D')D=make_pair(i,j);
		}
		vis[S.first][S.second]=1;
		puts(dfs(S.first,S.second,0)?"YES":"NO");
	}
	return 0;
}