hdu-1429（状压bfs）

#pragma warning (disable : 4996)

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<fstream>
#include<iomanip>
#include<string>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<stack>
#include<sstream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
using namespace std;

char pic[22][22];
bool vis[22][22][1 << 11];//对于每个格子，相同的状态只能经过一次
//表示出拥有钥匙的状态
int n, m, t;
int sx, sy, ex, ey;
int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };

struct node {
	int x, y, step, sta;
	node(){}
	node(int a, int b, int c, int d) {
		x = a;	y = b; step = c; sta = d;
	}
};

bool judge_range(int x, int y) {
	if (x < 0 || x >= m || y < 0 || y >= m || pic[x][y] == ‘*‘)	return false;
	return true;
}

bool judge_pass(int x, int y, int sta) {
	int res = pic[x][y] - ‘A‘;
	if ((sta & (1 << res)) == 0)	return false;
	return true;
}

int bfs() {
	queue<node> q;
	node from, to;
	q.push(node(sx, sy, 0, 0));
	vis[sx][sy][0] = 1;

	while (!q.empty()) {
		from = q.front();
		q.pop();

		if (from.step >= t)
			return -1;
		if (pic[from.x][from.y] == ‘^‘)
			return from.step;

		for (int i = 0; i < 4; ++i) {
			to = from;
			to.x += dir[i][0];
			to.y += dir[i][1];
			if (!judge_range(to.x, to.y))	continue;

			to.step++;
			char temp = pic[to.x][to.y];
			if (temp >= ‘A‘ && temp <= ‘Z‘ && !judge_pass(to.x, to.y, to.sta))	continue;
			if (temp >= ‘a‘ && temp <= ‘z‘) {
				int res = temp - ‘a‘;
				to.sta |= (1 << res);
			}
			
			if (vis[to.x][to.y][to.sta] == 0) {
				q.push(to);
				vis[to.x][to.y][to.sta] = 1;
			}
		}
	}
	
	return -1;
}

int main() {
	
	while (~scanf("%d %d %d", &n, &m, &t)) {
		memset(vis, 0, sizeof vis);
		for (int i = 0; i < n; ++i)	scanf("%s", pic[i]);

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < m; ++j) {
				if (pic[i][j] == ‘@‘)
					sx = i, sy = j;
				if (pic[i][j] == ‘^‘)
					ex = i, ey = j;
			}
		}

		printf("%d\n", bfs());
	}
	return 0;
}

hdu-1429（状压bfs）

原文：https://www.cnblogs.com/wanshe-li/p/13752355.html