hdu5025 状态压缩广搜

题意：

悟空要救唐僧，中途有最多就把钥匙，和最多五条蛇，要求就得唐僧并且拿到所有种类的钥匙（两个1只拿一个就行），拿钥匙i之前必须拿到钥匙i-1，打蛇多花费一秒，问救出唐僧并且拿到所有种类的钥匙的最小花费时间。

思路：

应该两种方法吧，感觉很多都是用4维的标记，然后广搜的，我用的是3维的标记，然后优先队列广搜的，题目没啥难的，关键是读懂题，敲代码的时候细心点就行了。mark[x][y][key] 表示在x,y点是要是状态是key是否走过。

#include<stdio.h>

#include<string.h>

#include<queue>

#define N 110



using namespace std;

typedef struct NODE

{

   int x ,y ,key ,t;

   int she;

   friend bool operator < (NODE a ,NODE b)

   {

      return a.t > b.t;

   }

}NODE;

NODE xin ,tou;

int mark[N][N][1<<10];

int  Map[N][N];

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

int ex ,ey ,n ,M;

int BFS(int x ,int y)

{

   priority_queue<NODE>q;

   xin.x = x ,xin.y = y ,xin.t = 0 ,xin.key = 0 ,xin.she = 0;

   memset(mark ,0 ,sizeof(mark));

   mark[xin.x][xin.y][xin.key] = 1;

   q.push(xin);

   while(!q.empty())

   {

      tou = q.top();

      q.pop();

      if(tou.x == ex && tou.y == ey && tou.key == (1 << M) - 1)

      {

         return tou.t;

      }

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

      {

         xin.x = tou.x + dir[i][0];

         xin.y = tou.y + dir[i][1];

         xin.t = tou.t + 1;

         if(xin.x < 1 || xin.x > n || xin.y < 1 || xin.y > n || !Map[xin.x][xin.y])

         continue;

         if(Map[xin.x][xin.y] >= 11)

         {

            if(tou.she & (1 << (Map[xin.x][xin.y] - 1)))

            xin.she = tou.she;

            else

            {

                xin.she = tou.she | (1 << (Map[xin.x][xin.y] - 1));

                xin.t ++;

             }

         }

         else xin.she = tou.she;

         if(Map[xin.x][xin.y] >= 1 && Map[xin.x][xin.y] <= 9)

         {

            if(Map[xin.x][xin.y] != 1 && !(tou.key & (1 << (Map[xin.x][xin.y] - 2))))

            xin.key = tou.key;

            else

            xin.key = tou.key | (1 << (Map[xin.x][xin.y] - 1));

         }

         else xin.key = tou.key;

         if(!mark[xin.x][xin.y][xin.key])

         {

            mark[xin.x][xin.y][xin.key] = 1;

            q.push(xin);

         }

      }

   }

   return -1;

}

int main ()

{

   int i ,j ,x ,y;

   char str[N];

   while(~scanf("%d %d" ,&n ,&M) && n + M)

   {

      int ss = 0;

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

      {

         scanf("%s" ,str);

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

         {

            if(str[j] == 'K')

            {

               x = i ,y = j + 1;

               Map[x][y] = 10;

            }

            if(str[j] == 'T')

            {

               ex = i ,ey = j + 1;

               Map[ex][ey] = 10;

            }

            if(str[j] == '.')

            Map[i][j+1] = 10;

            if(str[j] == '#')

            Map[i][j+1] = 0;

            if(str[j] >= '1' && str[j] <= '9')

            Map[i][j+1] = str[j] - '0';

            if(str[j] == 'S')

            {

               ss++;

               Map[i][j+1] = 10 + ss;

             }

         }

      }

      int Ans = BFS(x ,y);

      if(Ans == -1) puts("impossible");

      else printf("%d\n" ,Ans);

   }

   return 0;

}

巴特西

hdu5025 状态压缩广搜

最新文章

热门文章