hdu4771 水搜索（状态压缩+bfs）

题意：

给你一个n*m的地图，问你从起点出发，吧所有的宝藏都捡完用的最少时间。

思路：k <= 4,水题，直接开一个数组mark[now][x][y];now代表的是当前检宝藏的二进制压缩状态，然后就直接搜索就行了。

#include<stdio.h>

#include<string.h>

#include<queue>

#define N 100 + 5



using namespace std;

typedef struct

{

   int x ,y ,now;

}NODE;

NODE xin ,tou;

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

int map[N][N];

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

NODE K[5];

int n ,m ,k;

bool ok(int x ,int y ,int now)

{

   return x <= n && x >= 1 && y <= m && y >= 1 && !mark[now][x][y] && map[x][y];

}

int BFS(int sx ,int sy)

{

   queue<NODE>q;

   xin.x = sx ,xin.y = sy ,xin.now = 0;

   int mk = 0;

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

   if(xin.x == K[i].x && xin.y == K[i].y)

   {

      mk = i;

      break;

   }

   if(mk) xin.now = 0 | (1 << (mk - 1));

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

   q.push(xin);

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

   while(!q.empty())

   {

      tou = q.front();

      q.pop();

      if(tou.now == (1<<k) - 1)

      return mark[tou.now][tou.x][tou.y] - 1;

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

      {

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

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

         xin.now = tou.now;

         int mk = 0;

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

         if(xin.x == K[j].x && xin.y == K[j].y)

         {

            mk = j;

            break;

         }

         if(mk) xin.now = tou.now | (1<<(mk - 1));

         if(ok(xin.x ,xin.y ,xin.now))

         {

            mark[xin.now][xin.x][xin.y] = mark[tou.now][tou.x][tou.y] + 1;

            q.push(xin);

         }

      }

   }

   return -1;

}

int main ()

{

   int i ,j ,sx ,sy;

   char str[N];

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

   {

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

      {

         scanf("%s" ,str);

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

         {

            if(str[j-1] == '@')

            map[i][j] = 1 ,sx = i ,sy = j;

            if(str[j-1] == '.') map[i][j] = 1;

            if(str[j-1] == '#') map[i][j] = 0;

         }

      }

      scanf("%d" ,&k);

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

      scanf("%d %d" ,&K[i].x ,&K[i].y);

      printf("%d\n" ,BFS(sx ,sy));

   }

   return 0;

}

巴特西

hdu4771 水搜索（状态压缩+bfs）

最新文章

热门文章