题目地址: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"); else printf("YES\n"); scanf("%d %d %d",&n,&m,&t); }}