拯救大兵瑞恩 孤岛营救

// 拯救大兵瑞恩.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//



/*
* http://ybt.ssoier.cn:8088/problem_show.php?pid=1495
* https://loj.ac/p/6121
* https://www.luogu.com.cn/problem/P4011
【题目描述】
1944 年，特种兵麦克接到国防部的命令，要求立即赶赴太平洋上的一个孤岛，营救被敌军俘虏的大兵瑞恩。瑞恩被关押在一个迷宫里，
迷宫地形复杂，但幸好麦克得到了迷宫的地形图。迷宫的外形是一个长方形，其南北方向被划分为 n 行，东西方向被划分为 m 列， 
于是整个迷宫被划分为 n×m 个单元。每一个单元的位置可用一个有序数对 (单元的行号, 单元的列号) 来表示。
南北或东西方向相邻的 2 个单元之间可能互通，也可能有一扇锁着的门，或者是一堵不可逾越的墙。
迷宫中有一些单元存放着钥匙，并且所有的门被分成 p 类， 打开同一类的门的钥匙相同，不同类门的钥匙不同。

大兵瑞恩被关押在迷宫的东南角，即 (n,m) 单元里，并已经昏迷。迷宫只有一个入口， 在西北角。
也就是说，麦克可以直接进入 (1,1) 单元。另外，麦克从一个单元移动到另一个相邻单元的时间为 1，
拿取所在单元的钥匙的时间以及用钥匙开门的时间可忽略不计。

试设计一个算法，帮助麦克以最快的方式到达瑞恩所在单元，营救大兵瑞恩。

【输入】
第一行有三个整数,分别表示 n,m,p 的值。

第二行是一个整数k，表示迷宫中门和墙的总数。

第 i+2 行 (1≤i≤k)，有 5 个整数，依次为 xi1,yi1,xi2,yi2,gi:当 gi≥1 时，表示 (xi1,yi1)单元与 (xi2,yi2) 单元之间有一扇第 gi 类的门，
当 gi=0 时， 表示 (xi1,yi1) 单元与 (xi2,yi2) 单元之间有一堵不可逾越的墙。

第 k+3 行是一个整数 s，表示迷宫中存放的钥匙总数。

第 k+3+j 行 (1≤j≤s) ，有 3 个整数，依次为 xi1,yi1,qi​​​​ ，表示第 j 把钥匙存放在 (xi1,yi1) 单元里，并且第 j 把钥匙是用来开启第 qi 类门。

输入数据中同一行各相邻整数之间用一个空格分隔。

【输出】
输出麦克营救到大兵瑞恩的最短时间。如果问题无解，则输出 −1。

【输入样例】
4 4 9
9
1 2 1 3 2
1 2 2 2 0
2 1 2 2 0
2 1 3 1 0
2 3 3 3 0
2 4 3 4 1
3 2 3 3 0
3 3 4 3 0
4 3 4 4 0
2
2 1 2
4 2 1
【输出样例】
14
【提示】
|xi1−xi2|+|yi1−yi2|=1,0≤gi≤p
1≤qi≤p
n,m,p≤10,k<150
*/

#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>

using namespace std;


int n, m,p;
int k, s;

int calcid(int x, int y) {
	return x + y * 100;
}
void getposFromid(int n, int& x, int& y) {
	x = n % 100;
	y = n / 100;
}

int callongid(int x, int y, int a, int b) {
	return x + y * 100 + a * 10000 + b * 1000000;
}

void getposFromlongid(int n, int& x, int& y,int &a,int &b) {
	x = n % 100;
	y = n%10000 / 100;
	a = n % 1000000 / 10000;
	b = n / 1000000;
}

int calcpostate(int x, int y, int st) {
	return x + y * 100 + st * 10000;
}

void getposstatefromNum(int n, int& x, int& y, int& st) {
	x = n % 100;
	y = n % 10000 / 100;
	st = n / 10000;
}


unordered_map<int, int> doors;
unordered_map<int, int> keys;
unordered_map<int, int> vis;

int addx[] = { 1,0,-1,0 };
int addy[] = { 0,1,0,-1 };


void solve() {
	queue<int> q;
	q.push(calcpostate(1,1,0));
	//如果当前位置有钥匙 拿起钥匙
	vis[calcpostate(1, 1, 0| keys[calcid(1, 1)])]  = 1;

	while (q.size()) {
		auto t = q.front(); q.pop();
		int x = 0; int y = 0; int st = 0; int step = vis[t];
		getposstatefromNum(t, x, y, st);

		if (x == 1 && y == 2 && st == 4) {
			int ds = 9;
		}

		if (x == n && y == m) {
			cout << vis[t] - 1 << endl;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int a = x + addx[i]; int b = y+addy[i];
			if (a <= 0 || b <= 0 || a > n || b > m) continue;
			if (vis.count(calcpostate(a, b,st)) != 0) continue;
			//查看 xy ab之间是否有墙门
			if(doors.count(callongid(x, y, a, b)) != 0){
				int type = doors[callongid(x, y, a, b)];
				//有墙 就不必考虑
				if (type == 0) { continue; }
				else if (  (type & st)  != 0) {
					if (a == 1 && b == 3 && st == 0) {
						int ds = 9;
					}
					int newst = st | keys[calcid(a, b)];
					q.push(calcpostate(a, b, newst));
					vis[calcpostate(a, b, newst)] = step+1;
				}
			}
			else {
				if (a == 1 && b == 3 && st == 0) {
					int ds = 9;
				}
				//两个之间没有墙
				int newst = st | keys[calcid(a, b)];
				q.push(calcpostate(a, b, newst));
				vis[calcpostate(a, b, newst)] = step + 1;
			}
		}
	}
	

	cout << -1 << endl;
	return;
}

int main()
{
	cin >> n >> m >> p;
	cin >> k;
	for (int i = 1; i <= k; i++) {
		int x, y, a, b, t; cin >> x >> y >> a >> b >> t;
		if (t != 0) {
			t = 1 << t;
		}
		doors[callongid( x,  y, a, b)] = t;
		doors[callongid(a, b,x,y)] = t;
	}
	cin >> s;
	for (int i = 1; i <= s; i++) {
		int x, y, t;
		cin >> x >> y >> t;
		keys[calcid(x, y)] |= 1 << t;
	}
	solve();

	return 0;
}