BFS——1429 胜利大逃亡(续)

1429 胜利大逃亡(续)

题意：

思路：

本题的重点在于标记数组，除了基本的坐标$(x,y)$以外，在同一位置是否有某个钥匙显然会影响结果，所以这样一来，我们就要为每个钥匙拥有与否多开一维数组，这样总共就会有12维的标记数组。
但这样显然是不方便的，我们就可以用二进制数来代替，这就是状态压缩。
例子：

有钥匙$a$:
0000000001
有钥匙$b$:
0000000010
有钥匙$a和b$:
0000000011

AC代码：

判断某个钥匙是否拥有
temp.state&(1<<(a[tx][ty]-'A')

捡到某个钥匙
temp.state|(1<<(a[tx][ty]-'a'))

#include<bits/stdc++.h>const int N = 25,M = 2e5+10,INF = 0x3f3f3f3f;
struct Node{
    int x,y,state,step;
};int n,m,t,start_x,start_y,end_x,end_y;
int ne[4][2] = {
    0,1,1,0,0,-1,-1,0};
char a[N][N];
bool book[N][N][1024];void bfs()
{
    memset(book,false,sizeof book);std::queue<Node> que;que.push({
    start_x,start_y,0,0});book[start_x][start_y][0] = true;while(!que.empty()){
    auto temp = que.front();que.pop();if(temp.step >= t)continue;if(temp.x == end_x && temp.y == end_y){
    std::cout<<temp.step<<'\n';return;}for(int i = 0 ; i < 4 ; i++){
    int tx = temp.x + ne[i][0];int ty = temp.y + ne[i][1];if(tx<1||ty<1||tx>n||ty>m||a[tx][ty]=='*')continue;if(a[tx][ty]>='A'&&a[tx][ty]<='J'){
    if((temp.state&(1<<(a[tx][ty]-'A')))){
    if(!book[tx][ty][temp.state]){
    book[tx][ty][temp.state] = true;que.push({
    tx,ty,temp.state,temp.step+1});}}}else if(a[tx][ty]>='a'&&a[tx][ty]<='j'){
    int state = temp.state|(1<<(a[tx][ty]-'a'));if(!book[tx][ty][state]){
    book[tx][ty][state] = true;que.push({
    tx,ty,state,temp.step+1});}}else{
    if(!book[tx][ty][temp.state]){
    book[tx][ty][temp.state] = true;que.push({
    tx,ty,temp.state,temp.step+1});}}}}std::cout<<-1<<'\n';
}int main()
{
    
// std::ios::sync_with_stdio(false);
// std::cin.tie(nullptr);
// std::cout.tie(nullptr);while(std::cin>>n>>m>>t){
    for(int i = 1 ; i <= n ; i++){
    std::cin>>(a[i]+1);for(int j = 1 ; j <= m ; j++){
    if(a[i][j]=='@')start_x = i,start_y = j;else if(a[i][j]=='^')end_x = i,end_y = j;}}bfs();}return 0;
}