九度教程第92题
题目地址：http://jobdu.sinaapp.com/problem.php?cid=1040&pid=91
测试数据大放送：
4 4 5S.X...X...XD....3 4 5S.X...X....D2 2 1S..D8 8 7.DXS...X........XX..XX...X.X.X.X..X.....X....X..........XXXX....5 4 18S..................D6 6 10S..................................D2 3 2SDX..X2 2 3SD..2 2 2SDXX4 4 6.S..XXX.XXX.XXXD5 4 8S....XX..X...X.X....3 3 3333.S.......2 2 1SD..1 5 4S...D4 5 5.S.....X...XDX...X..2 4 7SD......2 2 3S.D.4 4 9S..XX.X...XD....0 0 0输出：NOYESNONONOYESNOYESNONONONOYESYESNOYESYESYES
#include<stdio.h>int mark[10][10];char s[10][10];int n,m,start1,start2,end1,end2,t,flag;void dfs(int i,int j,int time){if(flag==-1){if(time==t){if(i==end1&&j==end2)flag=1;}else {if(i>0&&mark[i-1][j]==-1&&s[i-1][j]!='X'){if(((time!=t-1)&&s[i-1][j]!='D')||((time==t-1)&&(s[i-1][j]=='D'))){mark[i-1][j]=1;dfs(i-1,j,time+1);mark[i-1][j]=-1;}}if(i<n-1&&mark[i+1][j]==-1&&s[i+1][j]!='X'){if(((time!=t-1)&&s[i+1][j]!='D')||((time==t-1)&&(s[i+1][j]=='D'))){mark[i+1][j]=1;dfs(i+1,j,time+1);mark[i+1][j]=-1;}}if(j<m-1&&mark[i][j+1]==-1&&s[i][j+1]!='X'){if(((time!=t-1)&&s[i][j+1]!='D')||((time==t-1)&&(s[i][j+1]=='D'))){mark[i][j+1]=1;dfs(i,j+1,time+1);mark[i][j+1]=-1;}}if(j>0&&mark[i][j-1]==-1&&s[i][j-1]!='X'){if(((time!=t-1)&&s[i][j-1]!='D')||((time==t-1)&&(s[i][j-1]=='D'))){mark[i][j-1]=1;dfs(i,j-1,time+1);mark[i][j-1]=-1;}}}}}int main(){int i,j;scanf("%d %d %d",&n,&m,&t);while(n||m||t){for(i=0;i<n;i++)scanf("%s",s[i]);for(i=0;i<n;i++)for(j=0;j<m;j++)mark[i][j]=-1;for(i=0;i<n;i++)for(j=0;j<m;j++)if(s[i][j]=='S')goto loop1;loop1:start1=i;start2=j;for(i=0;i<n;i++)for(j=0;j<m;j++)if(s[i][j]=='D')goto loop2;loop2:end1=i;end2=j;flag=-1;mark[start1][start2]=1;dfs(start1,start2,0);if(flag==-1)printf("NO\n");elseprintf("YES\n");scanf("%d %d %d",&n,&m,&t);}}