hdu 1010 미로 질문(DFS+ 가지치기)

/*

	  YY：

			      ，   DFS，         ，

			            

			    !!!      ，   ，    



*/





#include <stdio.h>

#include <math.h>

char s[105][105];

int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

int n,m,sum,si,sj,ei,ej,t;

int DFS(int x,int y,int num)

{

	if(num>t||x>=n||y>=m||x<0||y<0) return 0;//!!!!!!



//	if(s[x][y]=='D'&&num==t) {

//	 return 1;

//	}

	for(int i=0;i<4;i++)

    {

        if(s[x+dir[i][0]][y+dir[i][1]]=='D'&&num+1==t)

            return 1;

        if(s[x+dir[i][0]][y+dir[i][1]]=='.')

        {    

            s[x+dir[i][0]][y+dir[i][1]]='X';

            if(DFS(x+dir[i][0],y+dir[i][1],num+1))

                return 1;

            s[x+dir[i][0]][y+dir[i][1]]='.';

        }

    }

	return 0;//!!!!!

}

int main()

{

	int i,j,cas,x,y,wall;

	while(scanf("%d %d %d",&n,&m,&t)!=EOF&&n+m+t)

	{

		getchar();

		wall=0;

		for(i=0;i<n;i++)

		{

			for(j=0;j<m;j++)

			{

				scanf("%c",&s[i][j]);

				if(s[i][j]=='S') {si=i;sj=j;}

				if(s[i][j]=='D') {ei=i;ej=j;}

				if(s[i][j]=='X') {wall++;}

			}

			getchar();

		}

		

		if(abs(si-ei)+abs(sj-ej)>t||n*m-wall<t)//!!!!!!!!!!!!!!

        {

            printf("NO
");

            continue;

        }

        if((abs(si-ei)+abs(sj-ej))%2!=(t%2))//!!!!!!!!!!!!

        {

            printf("NO
");

            continue;

        } 	

		s[si][sj]='X';//!!!!!!!!!!!

		if(DFS(si,sj,0))

			printf("YES
");

		else

			printf("NO
");

	}

	return 0;

}