传送门
这道题就是HDU 1429 的加强版而已, 做过HDU1429的做这道题应该就会更有思路的多.
// 题意: 给定一个n*m的矩阵， 问从(1, 1)走到(n, m) 的最少步数是多少, 不过在某些点到某些点它可能有墙或者门, 墙不能被通过, 门的话必须要有相应的钥匙才行.
// 思路: 门只有10种, 很明显的处理方法就是很HDU1429一样, 用一个数的二进制位上时候有1来表示是否拥有这把钥匙, 还有就是标记状态也是一样的, 用三维矩阵来表示， 最后一维为拥有钥匙后的不同状态， 也就是拥有某把钥匙后走这个点后没有这把钥匙走过这个点的时候状态是不一样的. 有个难点就是它用的格子之间的边来表示的门和墙, 所以我们需要用一个四维的数组来表示门和墙. 具体细节请看代码.
注意一个坑点就是同一个地方可能会有多把钥匙, 所以你应该把他们都或起来. 开门是 & ， 捡钥匙是 | .
AC Code
const int maxn = 50+5;
int dx[] = {-1,1,0,0};
int dy[] = {0,0,-1,1};
bool vis[maxn][maxn][2050]; // 标记状态的.
int n,m,tot;
int sx,sy,ex,ey;
struct node
{
int x,y,t;
int key;
};
int a[maxn][maxn][maxn][maxn]; // 保存墙与门的信息
int g[maxn][maxn]; // 保存钥匙信息
bool ok(int x1, int y1, int x2, int y2, int key) {
int tmp = a[x1][y1][x2][y2];
if (!tmp) return false;
if (tmp > 0 && (key & (1<<tmp)) == 0) return false;
if (x2 < 1 || x2 > n || y2 < 1 || y2 > m) return false;
if (vis[x2][y2][key]) return false;
return true;
}
void bfs(int x,int y)
{
vis[x][y][0] = 1;
queue<node>q;
q.push(node{x, y, 0, g[x][y]});
while(!q.empty()){
node u = q.front();
q.pop();
if(u.x == ex && u.y == ey){
cout << u.t << endl;
return ;
}
for(int i = 0 ; i < 4 ; i ++){
int xx = u.x + dx[i];
int yy = u.y + dy[i];
if (!ok(u.x, u.y, xx, yy, u.key)) continue;
int kkey = u.key | g[xx][yy];
vis[xx][yy][kkey] = 1;
q.push(node{xx, yy, u.t + 1, kkey});
}
}
cout << -1 << endl;
}
void solve()
{
while(~scanf("%d%d%d",&n,&m,&tot)){
Fill(vis, 0); Fill(a, -1); Fill(g, 0);
sx = 1, sy = 1;
ex = n, ey = m;
int k ; cin >> k ;
for (int i = 1 ; i <= k ; i ++) {
int x1, y1, x2, y2, type;
cin >> x1 >> y1 >> x2 >> y2 >> type;
a[x1][y1][x2][y2] = a[x2][y2][x1][y1] = type;
}
int s ; cin >> s;
for (int i = 1 ; i <= s ; i ++) {
int x, y, k;
cin >> x >> y >> k;
g[x][y] |= (1<<k);
}
bfs(sx,sy);
}
}