posts - 99,  comments - 8,  trackbacks - 0
//典型的搜索题,这里采用深度优先搜索
//1.本题如果不注意剪枝很容易超时,这里有两处剪枝
//2.深度搜索时主要是处理:1.具体题目中如何定深度,本题以某一个合法位置的四个方向是同一深度所以for 循环中steps + 1
//                                              2.理解回溯的思想
//HDU 1010
#include <stdio.h>
#include 
<stdlib.h>

int dir[4][2= {{01}{-10}{0-1},{10}};
char block[9][9];  //迷宫数组 
int si, sj;        //入口 
int di, dj;        //出口 
int m, n, t;
int steps;
bool escape;

int DFS (int curx, int cury, int steps)
{
    //printf ("%d %d", curx, cury);
    if (curx < 0 || curx == 0 || cury < 0 || cury == 0 || curx > m || cury > n)  //该路径位置不合理,此次递归结束,但并不是整个递归结束
     return 0;
    
    if (curx == di && cury == dj && steps == t)
    escape = 1;
    
    //奇偶性剪枝
    int temp = 0;
    temp = (t - steps ) - abs (di - curx) - abs (dj - cury);   //处在该位置的深搜是否有可能到达终点 
    if (temp < 0 || temp & 1)  //当temp为奇数时 按位与是 1 ,temp为偶数时 按位是 0  
       return 0;
       
       if (escape)
       return 1;
    
    for (int i = 0; i < 4; i ++)
    {
        if (block[curx + dir[i][0]][cury + dir[i][1]] != 'X')  //因为也可以是D 
        {
           block[curx + dir[i][0]][cury + dir[i][1]] = 'X';
           DFS (curx + dir[i][0], cury + dir[i][1], steps + 1);
           block[curx + dir[i][0]][cury + dir[i][1]] = '.';
        }
    }
}

int main ()
{
     
while ( scanf ("%d%d%d"&m, &n, &t) && (m != 0 && n != 0 && t != 0))
     
{
           getchar ();
           
int wall = 0;
           
for (int i = 1; i <= m; i ++)
           
{
               for (int j = 1; j <= n; j ++)
               {
                   scanf ("%c", &block[i][j]);
                   
                   if (block[i][j] == 'S')  //入口坐标 
                   {
                      si = i; 
                      sj = j;
                   }
                  
                   if (block[i][j] == 'D')  //出口坐标 
                   {
                      di = i; 
                      dj = j;
                   } 
                   if (block[i][j] == 'X')
                   {
                      wall ++;
                   }  
               }
               getchar ();    //错点 
           } 
            
//printf ("%d %d", si, sj);
           /*for (int i = 1; i <= m; i ++)
           {
               for (int j = 1; j <= n; j ++)
               {  
                   printf ("%d", block[i][j]);
                   }
           }
*/

         
           
           
if ( m * n - wall < t)  //剪枝 
           {
                printf (
"NO\n");
                
continue;
           }


              escape 
= 0;
              steps 
= 0
              block[si][sj] 
= 'X'
              DFS (si, sj, steps);
              
              
if (escape)
              printf (
"YES\n");  
              
else
              printf (
"NO\n");
     }

     system (
"pause");
     
return 0;
}

posted on 2010-08-19 11:20 雪黛依梦 阅读(485) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(4)

随笔分类

随笔档案

文章档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜