九度教程第92题
测试数据大放送：
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++)
