//http://blog.csdn.net/vsooda/article/details/7884772
#include<iostream>

#include<math.h>

using namespace std;

char map[10][10];

int N,M,T;

int di,dj,escape;

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

void dfs(int x,int y,int cnt)

{

	if(x>N || y>M || x<1 || y<1 )

		return;

	if(cnt==T && x==di && y==dj)

		escape=1;

	if(escape==1)

		return;

	int temp = (T-cnt) - abs(x-di) - abs(y-dj);

	if(temp<0 || temp &1) //判断奇偶，剪枝

		return;

	for(int i=0;i<4;i++) //四个方向，堵住回去的路

	{

		if(map[x+dir[i][0]][y+dir[i][1]]!='X')

		{

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

			dfs(x + dir[i][0], y + dir[i][1], cnt+1);

			map[x+dir[i][0]][y+dir[i][1]]='.'; //恢复回去

		}

	}

	return;

}

int main()

{

	while(cin>>N>>M>>T, N)

	{

		int wall=0;

		int si,sj;

		for(int i=1;i<=N;i++)

			for(int j=1;j<=M;j++)

			{

				cin>>map[i][j];

				if(map[i][j]=='S')

				{

					si=i;

					sj=j;

				}

				else if(map[i][j]=='D')

				{

					di=i;

					dj=j;

				}

				else if(map[i][j]=='X')

					wall++;

			}

			if(T>=M*N-wall)

			{

				cout<<"NO"<<endl;

				continue;

			}

			map[si][sj]='X';

			escape=0;

			dfs(si,sj,0);

			if(escape==1)

				cout<<"YES"<<endl;

			else

				cout<<"NO"<<endl;

	}

}

  temp of the bone 

 sample input:

 S.X.

 ..X.

 ..XD

 ....

 问题：

 ():

 在发现当前节点无法到达时,这点弹出栈,并且把这点的标记重新刷为'.'

 ():

 如何在dfs中既要保证到达又要使时间正好呢?? 在函数中通过这种形式实现:

 dfs(int si,int sj,int cnt) 就是用cnt来记录当时的时间,并且在

 if( si==di && sj==dj && cnt==t )

     {

         escape = ;

         return;

     }

 的时候 即当前点到达了终点并且时间恰好等于题目所给限制时间时,跳出

 并且escape标记为真

 ():

 如何让一个点有顺序地遍历它四周地能到达的点呢??

 聪明并且简短的方法是设施一个dir[][] 数组 控制方向

 并且设置它的值为dir[][]={{,-},{,},{,},{-,}};

 遍历的时候用for(i:->)就非常方便了

 ():

 千万要注意的是节点越界的情况, dfs(int si,int sj,int cnt)的时候一定要把 si, sj 控制在给你的矩阵内 在后面会提到一个我的列子 就是因为访问了[, -]的位置导致了其

 他数据被更改

 ():

 读入矩阵的时候,可以采用for(i = ; i <= N; i++)

                for(j = ; j <= M; j++)

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

 的方法,好处在于可以控制和计算每一个读入的数据,坏处是调试的时候对矩阵的观察不太方便,而且好像还会有错误,在2102"A计划"用这种方法读入数据时好像就会wa,

 另一种方法是for(i = ; i < N; i++) gets(map[i]);

 这样读入的数据在调试观察的时候十分方便 gets()读入的默认为字符串,在vc调试的时候是显式的 可以直接观察矩阵 缺点是对矩阵中各个数据的计算和控制无法实现,需要读完后再遍历一遍

 ()

 能用bfs还是尽量用bfs 我不会bfs.... dfs的递归在调试的时候不是很方便,而且bfs要比dfs快,调试也要方便,因为它没有递归

 ()

 关于剪枝,没有剪枝的搜索不太可能,这题老刘上课的时候讲过两个剪枝,一个是奇偶剪枝,一个是路径剪枝

 奇偶剪枝:

 把矩阵标记成如下形式:

 ,,,,

 ,,,,

 ,,,,

 ,,,,

 很明显,如果起点在0 而终点在1 那显然 要经过奇数步才能从起点走到终点,依次类推,奇偶相同的偶数步,奇偶不同的奇数步

 在读入数据的时候就可以判断,并且做剪枝,当然做的时候并不要求把整个矩阵0,1刷一遍,读入的时候起点记为(Si,Sj) 终点记为(Di,Dj) 判断(Si+Sj) 和 (Di+Dj) 的奇偶性就可以了

 路径剪枝:

 矩阵的大小是N*M 墙的数量记为wall 如果能走的路的数量 N*M - wall 小于时间T,就是说走完也不能到总的时间的,这显然是错误的,可以直接跳出了

 课件里面给过这题的标程,在dfs的过程中有个没提到的剪枝,就是记录当前点到终点的最短路,如果小于剩余的时间的话,就跳出

 这个剪枝我觉得更科学,它毕竟是动态的么,标程里面是这么写的:

 temp = (t-cnt) - abs(si-di) - abs(sj-dj);

 if( temp< || temp& ) return;

 其中求当前点到终点的最短路是这样 abs(si-di) - abs(sj-dj) 这个就比较粗糙了 明显没有考虑到碰到墙要拐弯的情况

 那求最短路有没有什么好办法呢?

 我曾经想到过用 Dijkstraq求最短路的 ,明显大才小用,在论坛里看到一个方法觉得可以用在这里

 给定下例:

 S.X.

 ..X.

 ..XD

 ....

 每个点到终点的最短路是不是这样呢:

 S6X2

 65X1

 54XD

 这怎么求呢??从终点开始遍历整个数组,终点是0,它周围的点都+,墙就不计数,依次类推,就能求得这个矩阵的一个最短时间矩阵,在dfs的时候比较当前点到终点的最短路,如果大于剩余时间的话就跳出

 这个方法的预处理还是非常快的,我没有用过,但是感觉会非常有用处.

 ()

 在做这题的时候,我碰到过一个神奇的事情,在程序运行至下面代码时

 if( map[ si+dir[i][] ][ sj+dir[i][] ] != 'X')

     map[ si+dir[i][] ][ sj+dir[i][] ] = 'X';

 T被改变了!! 这丝毫和T没有关系啊,怎么改变T的值呢??

 原来在起点map[][]进入时,我没有注意到map[ si+dir[i][] ][ sj+dir[i][] ] 实际做的是map[][-] = 'X'; 很危险的一个赋值,书本上千万次强调的东西让我碰上了,这个地方我找了很久,因此我觉得有必要单独列出来提醒自己

 //////////////////////////////////////////////////////////////////////////////////////////////////////////////

 下面我把一个带注释的标程贴一下,不是我写的注释

 //zju 2110 Tempter of the Bone

 #include <stdio.h>

 #include <iostream>

 #include <string.h>

 #include <stdlib.h>

 using namespace std;

 //迷宫地图

 //X: 墙壁，小狗不能进入

 //S: 小狗所处的位置

 //D: 迷宫的门

 //. : 空的方格

 char map[][];

 int n,m,t,di,dj; //(di,dj):门的位置

 bool escape;

 int dir[][]={{,-},{,},{,},{-,}}; //分别表示下、上、左、右四个方向

 void dfs(int si,int sj,int cnt)  //表示起始位置为(si,sj)，要求在第cnt秒达到门的位置

 {

     int i,temp;

     if( si>n || sj>m || si<= || sj<= ) return;

     if( si==di && sj==dj && cnt==t )

     {

         escape = ;

         return;

     }

     //abs(x-ex) + abs(y - ey)表示现在所在的格子到目标格子的距离（不能走对角线）

     //t-cnt是实际还需要的步数，将他们做差

     //如果temp < 0或者temp为奇数，那就不可能到达！

     temp = (t-cnt) - abs(si-di) - abs(sj-dj);

     if( temp< || temp& ) return; 

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

     {

         if( map[ si+dir[i][] ][ sj+dir[i][] ] != 'X')

         {

             map[ si+dir[i][] ][ sj+dir[i][] ] = 'X';

                 dfs(si+dir[i][], sj+dir[i][], cnt+);

             if(escape) return;

             map[ si+dir[i][] ][ sj+dir[i][] ] = '.';

         }

     }

     return;

 }

 int main()

 {

     int i,j,si,sj;

     while( cin >> n >> m >> t)

     {

         if( n== && m== && t== )

             break;

         int wall = ;

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

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

             {

                 cin >> map[i][j];

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

                 else if( map[i][j]=='D' ) { di=i; dj=j; }

                 else if( map[i][j]=='X' ) wall++;

             }

             if( n*m-wall <= t )

             {

                 cout << "NO" << endl;

                 continue;

             }

             escape = ;

             map[si][sj] = 'X';

             dfs( si, sj,  );

             if( escape ) cout << "YES" << endl;

             else cout << "NO" << endl;

     }

     return ;

 }

 这个注释当初还是帮了我很大忙的,起码让我看懂了课件