获取所有钥匙的最短路径（二进制状态压缩）

description

给定一个二维网格 grid。
“.” 代表一个空房间， “#” 代表一堵墙， “@” 是起点，（”a”, “b”, …）代表钥匙，（”A”, “B”, …）代表锁。

我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。

如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 K 为钥匙/锁的个数，且满足 1 <= K <= 6，字母表中的前 K 个字母在网格中都有自己对应的一个小写和一个大写字母。

换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。

另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

输出获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。

方法

1.

  • 用一个数代表题目给出的钥匙数目（$1<=k<=6$）6个二进制位表示每个钥匙存在（bfs结束的条件）,然后bfs跑一遍图，每个点有多个状态，（不仅 包括当前点钥匙，还有以前的拿的钥匙）
    所以每个点存step 和当前手里拥有的 key ，标记经过的状态vis[x][y][key],走过就不在入队了
    • 每个点是否有钥匙拿，是否有钥匙解锁，墙不能走，
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      #include<iostream>
      #include<queue>
      using namespace std;
      struct node{
          int sta;
          int x;
          int y;
          int step;
          node(int a,int b,int c,int d){
              sta=a;x=b;y=c;step=d;
          }
      };
      int n,m;
      int sx,sy;
      int ansstates=0;
      int next1[4][2]={0,1,1,0,0,-1,-1,0};
      bool vis[35][35][65];// 2^6==64
      char grid[35][35];

      int bfs(){
          queue<node> que;
          que.push(node(0,sx,sy,0));
          vis[sx][sy][0]=1;//标记当前点拥有第0个钥匙的状态走过
          while(!que.empty()){
              node head=que.front();
              que.pop();
              for(int i=0;i<4;i++){
                  int sta=head.sta,x=head.x,y=head.y,step=head.step;
                  int tx=x+next1[i][0];
                  int ty=y+next1[i][1];
                  if( tx>=1 && ty>=1 && tx<=n && ty<=m &&(grid[tx][ty]!='#')){
                      char c=grid[tx][ty];

                      if(islower(c))  sta|=1<<(c-'a'); //在原来的基础上捡
                      else if(isupper(c) && !(sta>>(c-'A'))&1 ) continue;//遇到们，没有钥匙，就continue
                      if( !vis[tx][ty][sta] ){//遇到门有钥匙，判断该点拥有的钥匙状态是否遍历过，没有就入队
                      //每次捡到钥匙后还要判断钥匙是否都有了
                          if(sta == ansstates) return step+1;
                          vis[tx][ty][sta]=true;
                          que.push(node{sta,tx,ty,step+1});
                      }
                  }
              }

          }
          return -1;
      }
      int main(){
          freopen("a.txt","r",stdin);
          cin>>n>>m;getchar();
          for(int i=1;i<=n;i++){
              for(int j=1;j<=m;j++){
                  scanf("%c",&grid[i][j]);
                  if( grid[i][j]=='@' ) sx=i,sy=j;
                  if( grid[i][j]>='a'&&grid[i][j]<='f') ansstates=max(ansstates,ansstates|1<<(grid[i][j]-'a') );
              }
              getchar();
          }
          cout<<bfs()<<endl;
          return 0;
      }

2.（大佬教我的）用hash的思想，表示每个点拥有不同的钥匙的状态，

  • 核心没变，每个点拥有的钥匙状态还是二进制压缩，只是判重变了.
  • key[]用来记录题目给出的钥匙,ha[hashnum]代表每个点拥有的钥匙的不同状态是否遍历过，（hashnum为hash函数映射出来的值）
  • hashnum只要放缩成不重复的就行（随意放缩）
  • 这个方法每一步拿自己的钥匙，上一种解法（当前点拿下一步的钥匙）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    #include<iostream>
    #include<queue>
    #include<unordered_map>
    using namespace std;
    struct node{
        int sta;
        int x,y;
        int step;
        node(int a,int b,int c,int d){
            sta=a;x=b;y=c;step=d;
        }
    };
    int next1[4][2]={0,1,1,0,0,-1,-1,0};

    int n,m;
    char grid[35][35];
    // bool vis[35][35][65];// （111111）2^6个状态
    unordered_map<char,bool> key;
    unordered_map<int,bool> ha;
    queue<node> que;

    int hashNode(node x){
        int res=0;
        res+=(x.x<<15);
        res+=(x.y<<10);
        res+=x.sta;
        return res;
    }
    bool check(node x){
        for(int i='a';i<='f';i++){
                if(key[i]){
                    if( x.sta & 1<<(i-'a') ) continue;
                    else return false;
                }
        }
        return true;
    }
    int bfs(){
        while(!que.empty()){
            node head=que.front();
            que.pop();
            //判断该点钥匙状态是否走过
            int hashnum=hashNode(head);
            if(ha[hashnum]) continue;
            else ha[hashnum]=true;

            char c=grid[head.x][head.y];

            if( c<='f' && c>='a') head.sta|=1<<(c-'a');//捡钥匙

            if( check( head ) ) return head.step;
            
            //该点是锁
            if( c<='F' && c>='A')
                if(!head.sta & 1<<(c-'A'))   continue;//跳过

            for(int i=0;i<4;i++){
                int tx=head.x+next1[i][0];
                int ty=head.y+next1[i][1];
                if( tx>=1 && ty>=1 && tx<=n && ty<=m && (grid[tx][ty]!='#')){
                    que.push(node{head.sta,tx,ty,head.step+1});
                }
            }
        }
        return -1;
    }
    int main(){
        freopen("a.txt","r",stdin);
        cin>>n>>m;getchar();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                grid[i][j]=getchar();
                if(grid[i][j]=='@') que.push( node{0,i,j,0} );
                if(grid[i][j]<='f' && grid[i][j]>='a')
                    key[grid[i][j]]=true;
            }
            getchar();
        }
        cout<<bfs();
        return 0;
    }