測試數據大放送： 4 4 5 S.X. ..X. ..XD .... 3 4 5 S.X. ..X. ...D 2 2 1 S. .D 8 8 7 .DXS...X ........ XX..XX.. .X.X.X.X ..X..... X....X.. ........ XXXX.... 5 4 18 S... .... .... .... ...D 6 6 10 S..... ...... ...... ...... ...... .....D 2 3 2 SDX ..X 2 2 3 SD .. 2 2 2 SD XX 4 4 6 .S.. XXX. XXX. XXXD 5 4 8 S... .XX. .X.. .X.X .... 3 3 3333 .S. ... ... 2 2 1 SD .. 1 5 4 S...D 4 5 5 .S... ..X.. .XDX. ..X.. 2 4 7 SD.. .... 2 2 3 S. D. 4 4 9 S..X X.X. ..XD .... 0 0 0 輸出： NO YES NO NO NO YES NO YES NO NO NO NO YES YES NO YES YES YES C語言源碼： [cpp] #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); } }
