Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 88587 Accepted Submission(s): 24116
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char map[10][10];
int p[4][2]={{-1,0},{1,0},{0,1},{0,-1}};//方向,刚学,代码写的挫
int i,j,flag,n,m,t,stx,sty,enx,eny;
int abs(int a){
return a>0?a:-a;
}
void dfs(int x,int y,int k)
{
if(t==k&&enx==x&&eny==y)
flag=1;
if(flag)
return;//不知道当初为什么这么写,直接return不就好了吗,日哦,可能刚开始学掌握的不好吧,好多代码都是参考别人的才写出来的
int v=t-k-abs(enx-x)-abs(eny-y);//两个剪枝,v小于0时就是剪枝1,判断v的奇偶,剪枝2
if(v<0||v&1)
return;
for(int i=0;i<4;i++)
{
int xx=p[i][0]+x;
int yy=p[i][1]+y;//枚举方向
if(xx>=0&&xx<n&&yy>=0&&yy<m&&map[xx][yy]!=‘X‘)
{
map[xx][yy]=‘X‘;
dfs(xx,yy,k+1);
map[xx][yy]=‘.‘;//回溯
}
}
}
int main(){
while(scanf("%d%d%d",&n,&m,&t)){
if(n+m+t==0) break;
for(i=0;i<n;i++){
cin>>map[i];
for(j=0;j<m;j++){
if(map[i][j]==‘S‘){
stx=i;
sty=j;
}//记录起点和终点
if(map[i][j]==‘D‘){
enx=i;
eny=j;
}
}
}
map[stx][sty]=‘X‘;
flag=0;
dfs(stx,sty,0);
if(flag) printf("YES\n");
else printf("NO\n");
}
return 0;
}
原文:http://www.cnblogs.com/wabi87547568/p/4687875.html