BFS + 状态压缩优化

例题
HDOJ1429 胜利大逃亡(续)

题目描述

Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……

这次魔王汲取了上次的教训，把Ignatius关在一个n*m的地牢里，并在地牢的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试，Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。

Input

每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图，其中包括:

. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙，对应的门分别为A-J

每组测试数据之间有一个空行。

Output

针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开，如果不能则输出-1。

Sample Input

4 5 17
@A.B.
a..
..^
c..b*

4 5 16
@A.B.
a..
..^
c..b*

Sample Output

16
-1

问题分析

本题的访问状态不能直接定义为已访问和未访问，因为有些地板可能需要拿到钥匙以后再来访问。而一共有十把钥匙，必须要把所有钥匙的组合可能性都列出来。我们可以给vis数组开三维数组。用二进制来表示钥匙的情况，一共有2^10 = 1024种可能性。这就叫做状态压缩。

代码

//BFS + 状态压缩
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cctype>
using namespace std;
char map[25][25];
int dir[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};
int vis[25][25][1050];
int n,m,t,sx,sy;
struct Node
{
  int y,x;
  int key;
  int cnt;
};

int bfs()
{
  queue<Node> q;
  memset(vis,0,sizeof(vis));
  Node start = {sy,sx,0,0};
  vis[sy][sx][0] = 1;
  q.push(start);
  while(!q.empty())
  {B
    Node f = q.front();q.pop();
    if(f.cnt >= t)  continue;
    if(map[f.y][f.x] == '^')  return f.cnt;
    for(int i=0;i<4;i++)
    {
      int ny = f.y + dir[i][0];
      int nx = f.x + dir[i][1];
      if(ny < 1 || ny > n || nx < 1 || nx > m || map[ny][nx] == '*')  continue;
      else if(vis[ny][nx][f.key] == 1)  continue;
      else if(isupper(map[ny][nx]))
      {
       /*  map[ny][nx] - 'a'+1 就是第n把钥匙处在的位置，我们把它向右移动到第一位，再&1，就可以判断是否有这一把钥匙 */
        if(f.key >> (map[ny][nx] - 'A') & 1)
        {
          vis[ny][nx][f.key] = 1;
          Node now = {ny,nx,f.key,f.cnt+1};
          q.push(now);
        }
      }
      else if(islower(map[ny][nx]))
      {
         //用或操作符来增加钥匙
        Node now = {ny,nx,f.key|(1<<(map[ny][nx] - 'a')),f.cnt+1};
        vis[ny][nx][now.key] = 1;
        q.push(now);
      }
      else
      {
        Node now = {ny,nx,f.key,f.cnt+1};
        vis[ny][nx][f.key] = 1;
        q.push(now);
      }
    }
  }
  return -1;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  while(cin >> n >> m >> t)
  {
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
      cin >> map[i][j];
      if(map[i][j] == '@')
      {
        sy = i;
        sx = j;
        map[i][j] = '.';
      }
    }
    int ans = bfs();
    cout << ans << endl;
  }
}