HDU 1429(状压+bfs)
题意：在T-1时间内逃出城堡，途中可能会遇到10种门或钥匙，每种门对应一种钥匙。
julyc的代码告诉了我也可以这么用：
继续加油~
思路：
简单的bfs，但是判断一个点能否通过不是简单的判断是否走过，而是判断通过该点时拥有的钥匙的状态是否一致。
所以，判重的check数组要多开一维，表示钥匙的状态。状态表示的思想其实就是用一个数值将每一层的情况给表示出来，而状态压缩是用位运算来简化这种表示方法。所以这里用二进制的10个位分别表示每一种钥匙的状态。
#include <algorithm>
#include <iostream>
#include <string.h>
#include <ctype.h>
#include <cstdio>
#include <queue>
using namespace std;
struct node{
int x, y, sta, time;
node(int a, int b, int c, int d):x(a),y(b),sta(c),time(d){}
};
int nt[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int n, m, t, sx, sy, ex, ey;
int check[25][25][1<<10];
char map[25][25];
queue<node> q;
int bfs()
{
int tx, ty, tsta, jc;
check[sx][sy][0] = 1;
q.push(node(sx, sy, 0, 0));
while(!q.empty())
{
node tp = q.front();
q.pop();
if(tp.time >= t) break; //剪枝
for(int i = 0; i < 4; ++i)
{
tx = tp.x + nt[i][0];
ty = tp.y + nt[i][1];
if(tx < 0 || tx >= n || ty < 0 || ty >= m) continue;
if(map[tx][ty] == '*') continue;
tsta = tp.sta;
if(islower(map[tx][ty]))
{
//如果是钥匙，更改tsta判断拿没拿过
tsta = (tp.sta | (1<<(map[tx][ty]-'a')));
}
else if(isupper(map[tx][ty]))
{
//如果是门，判断拿没拿此门的钥匙
jc = (tp.sta & (1<<(map[tx][ty]-'A')));
if(!jc) continue;
}
//如果以tsta状态走过该坐标，continue
if(check[tx][ty][tsta]) continue;
if(map[tx][ty] == '^')
{
if(t-tp.time-1 > 0) return tp.time+1;
return -1;
}
check[tx][ty][tsta] = 1;
q.push(node(tx, ty, tsta, tp.time+1));
}
}
return -1;
}
int main()
{
while(~scanf("%d %d %d", &n, &m, &t))
{
memset(check, 0, sizeof check);
while(!q.empty()) q.pop();
for(int i = 0; i < n; ++i)
{
scanf("%s", map[i]);
for(int j = 0; j < m; ++j)
{
if(map[i][j] == '@') sx = i, sy = j;
}
}
cout << bfs() << endl;
}
return 0;
}看到julyc学长写的代码，知道了放入队列时还可以通过强制转换为结构体进行赋值。
平时我们都这么用：
struct node{
int x, y;
node(){}
node(int a, int b):x(a), y(b){}
};
q.push(node(tx, ty));julyc的代码告诉了我也可以这么用：
struct node{
int x, y;
};
q.push((node){tx, ty});继续加油~