hdu1429.MD

日期 2021 / 11 / 4

题目

[题目链接]https://acm.dingbacode.com/showproblem.php?pid=1429

胜利大逃亡(续)

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 14029 Accepted Submission(s): 5055

Problem Description

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

解题思路

这个题目虽然是一个bfs的题目，但是里面穿插了状态压缩的思想，题目除了说了一般bfs里面有的墙不能走的条件外还加了一个用钥匙打开的门的选项，这里我是在结构体里面多 加了一个变量k来判断此时能不能打开门，如果我们捡到一把钥匙，那我们对其进行 b.k = b.k | (1 << (map1[b.x][b.y] - 'a')); 操作，使其相应位数上的数 变为1，比如说我有a,b,e这三把钥匙，那么我此时的k的二进制就表示...10011，用了位运算就巧妙的解决了钥匙问题，如果我们碰到一个门，那么进行 int k = b.k & (1 << (map1[b.x][b.y] - 'A')); 判断，如果k不为0就证明有这个钥匙，因为1 & 0 == 0， 1 & 1 == 1，如果有钥匙那么它对应位数上的数就是1，进行&运算就不会等于0.这里的vis数组我定义为3维的，因为 多了钥匙这个状态，对于每一个点，访问的时候钥匙的数量也是不一定的，而且这个数组的大小是2^0到2^9的值相加，为1000左右，此时为拥有全部钥匙。因为题目中钥匙的种类是'a'到’j'刚好9位， 如果钥匙种类更大就不能再用数组存了.

代码演示

#include <iostream>
#include <queue>
#include <cmath>

#define INF 0x7fffffff
#define rep(x, y, z) for (int x = y; x <= z; x++)
#define dec(x, y, z) for (int x = y; x >= z; x--)
#define format(a) memset (a, 0, sizeof(a))
#define swap(a, b) (a ^= b ^= a ^= b)
#define ll long long int
#define ull unsigned long long int 
#define uint unsigned int
const int maxn = 1e6 + 10;
using namespace std;

int n, m, t, sx, sy, ex, ey, flag, ans;
int dir[][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
int vis[25][25][5000];
char map1[25][25];
char c;

typedef struct Mix {
  int x;
  int y;
  int k;
  int time;
} node;

void bfs() {
  node a, b;
  queue<node> q;
  a.x = sx;
  a.y = sy;
  a.time = a.k = 0;
  q.push(a);
  while (q.size()) {
    a = q.front();
    q.pop();
    if (a.time >= t) {
      return;
    }
    if (a.x == ex && a.y == ey) {
      flag = 1;
      ans = a.time;
      break;
    }
    for (int i = 0; i < 4; i++) {
      b.x = a.x + dir[i][0];
      b.y = a.y + dir[i][1];
      b.time = a.time + 1;
      b.k = a.k;
      if (b.x >= 0 && b.x < n && b.y >= 0 && b.y < m && map1[b.x][b.y] != '*' && !vis[b.x][b.y][b.k]) {
        if ('a' <= map1[b.x][b.y] && map1[b.x][b.y] <= 'z') {
	  b.k = b.k | (1 << (map1[b.x][b.y] - 'a'));
	  vis[b.x][b.y][b.k] = 1;
	  q.push(b);
	}
        else if ('A' <= map1[b.x][b.y] && map1[b.x][b.y] <= 'Z') {
	  int k = b.k & (1 << (map1[b.x][b.y] - 'A'));
	  if (k) {
	    vis[b.x][b.y][b.k] = 1;
	    q.push(b);
	  }
	} else {
	  vis[b.x][b.y][b.k] = 1;
	  q.push(b);
	}
      }
    }
  }
}

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  while (cin >> n >> m >> t) {
    flag = ans = 0;
      for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
	  cin >> c;
	  map1[i][j] = c;
	  if (c == '@') {
	    sx = i;
	    sy = j;
	  }
	  if (c == '^') {
	    ex = i;
	    ey = j;
	  }
	}
	getchar();
      }
      bfs();
      format(vis);
      if (flag) {
        cout << ans << endl;
      } else {
        cout << -1 << endl;
      }
  }
  return 0;
}