LeetCode-获取所有钥匙的最短路径(BFS+状态压缩)

末蓝、 2022-02-19 23:19 236阅读 0赞

# [NCSTOJ-获取所有钥匙的最短路径][NCSTOJ-] #

# [LeetCode-864. 获取所有钥匙的最短路径][LeetCode-864.] #

### Description ###

给定一个二维网格 grid。

“.” 代表一个空房间， “\#” 代表一堵墙， “@” 是起点，（“a”, “b”, …）代表钥匙，（“A”, “B”, …）代表锁。

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

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

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

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

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

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

### Input ###

整数n, m，代表grid的行、列 （1 ≤ n,m ≤ 30）

以下为n\*m的矩阵

### Output ###

获取所有钥匙所需要的移动的最少次数

### Sample Input ###

3 5
    @.a.#
    ###.#
    b.A.B

### Sample Output ###

### 思路 ###

> 最近在看状态压缩，但还是一知半解，做这道题前听说会用到状压，所以做的时候总在想怎么去状压，结果搞了两个晚上才搞出来。第一天晚上当成普通的bfs写的，结果提交时发现有了反例，因此这么写行不通。这道题在bfs上又多加了个状态，记得曾经写过一道题，poj4115鸣人与佐助，那道题也加了个状态，手中查克拉的数量。所以需要多定义个变量来保存状态。接着有着这个思路，又在自己写的bfs基础上加了个状态保存，用一个三维数组来保存每种状态。可后来又发现，还是有点不同的，这道题是一把钥匙配一把锁，而那道题只要手中有查克拉，就能打到一个手下。所以这道题还要保存下当前手中有哪些钥匙，那要不就用一个book数组来保存当前手中的钥匙吧，但这种全局数组还是不能满足当前手中的钥匙量，也就是说bfs沿着两条不同的路走，分别搜索钥匙，搜到就存到数组中，但这样就是共享一个数组了，分不清沿着这条路走，其中一把钥匙是在这条路上还是不在。所以这回就想到了最近学的状压了，哈哈，刚好，位进制可以表示一种状态，每走一步就有一个状态，这个状态是独立的，只归这一步所有。与其他的不受影响。  
> 这样初始化状态，题目中说最多6把钥匙，数据量也不大。选取1<<k-1为最终状态量，记0表示没有，1表示有，那11111表示所有钥匙都找到了，00000就是初始状态。并且这种状态表示法，还能取出相应位置上的状态，比如走到一把锁面前，想知道目前是否有匹配的钥匙，那就取出所对应的钥匙位。当找到一把钥匙了，那就把该钥匙位变为1，直到所有钥匙位都变为1时，所有的钥匙就都找到了。

### LeetCode ###

struct Step
    { 
        int x;
        int y;
        int ck; //目前手中钥匙的状态
        Step(int x,int y,int ck):x(x),y(y),ck(ck){ }
    };
    class Solution { 
    public:
        queue<Step> que;
        bool vis[35][35][1<<7]={ false}; //标记当前状态是否被拓展
        const int dis[4][2]={ 0,1,1,0,0,-1,-1,0};
        int shortestPathAllKeys(vector<string>& grid) { 
    
            int len1=grid.size();
            int len2=grid[0].length();
            int k=0; //记录钥匙的数量
            for(int i=0;i<len1;i++)
            { 
                for(int j=0;j<len2;j++)
                { 
                    if(grid[i][j]>='a'&&grid[i][j]<='z') k++;
                    if(grid[i][j]=='@')
                    { 
                        que.push(Step(i,j,0));
                        vis[i][j][0]=true;
                    }
                }
            }
            int steps=0;
            while(!que.empty())
            { 
                int l=que.size();
                while(l--)
                { 
                    Step u=que.front();
    
                    que.pop();
                    for(int i=0;i<4;i++)
                    { 
                        int dx=u.x+dis[i][0];
                        int dy=u.y+dis[i][1];
                        int x=u.ck; //取出当前状态
                        
                        if(dx>=0&&dx<len1&&dy>=0&&dy<len2)
                        { 
                            char ch=grid[dx][dy];
                            if(ch=='#'||vis[dx][dy][x]) continue;
                            if(ch>='a'&&ch<='z')
                            { 
                                x=x|(1<<(ch-'a')); //将该位变为1
                                if(x==((1<<k)-1))
                                { 
                                    return steps+1;
                                }
                            }
                            if(ch>='A'&&ch<='Z')
                            { 
                                if(!(x>>(ch-'A')&1)) //判断当前位是否是1
                                { 
                                    continue;
                                }
                            }
                            vis[dx][dy][x]=true;
                            que.push(Step(dx,dy,x));
                        }
                    }
                }
                steps++; //步数加1
            }
            return -1;
        }
    };

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <queue>
    #include <vector>
    using namespace std;
    struct Node
    { 
        int x;
        int y;
        int ck; //身上目前拥有的钥匙状态
        int steps; //步数
        Node(int x,int y,int ck,int s):x(x),y(y),ck(ck),steps(s){ }
    };
    int n,m; // n行m列
    vector<vector<char> > vec;
    bool usr[35][35][1<<7]={ false}; //表示在i,j处身上有的钥匙，该状态是否被拓展
    int k; //记录钥匙的个数
    queue<Node> que;
    //int book[7]; //标记手中有的钥匙
    const int dis[4][2]={ 0,1,1,0,0,-1,-1,0};
    int main()
    { 
         // freopen("test.txt","r",stdin);
        cin>>n>>m;
        vec.resize(n+1,vector<char>(m+1));
        for(int i=0;i<n;i++)
        { 
            for(int j=0;j<m;j++)
            { 
                cin>>vec[i][j];
                if(vec[i][j]>='a'&&vec[i][j]<='z') k++;
                if(vec[i][j]=='@') 
                { 
                    que.push(Node(i,j,0,0));
                    usr[i][j][0]=true;
                    vec[i][j]='.'; //将起点变为道路，方便后面遍历，在这坑了好长时间，后来走了一遍发现起点这有问题
                }
            }
        }
        bool flag=false;
        while(!que.empty())
        { 
            Node p=que.front();
            que.pop();
            if(flag) break;
            for(int i=0;i<4;i++)
            { 
                int dx=p.x+dis[i][0];
                int dy=p.y+dis[i][1];
                if(dx>=0&&dx<n&&dy>=0&&dy<m)
                { 
                    char ch=vec[dx][dy];
                    int x=p.ck;
                    if(vec[dx][dy]=='#'||usr[dx][dy][x]) continue;
                    if(vec[dx][dy]=='.')
                    { 
                        que.push(Node(dx,dy,x,p.steps+1));
                        usr[dx][dy][x]=true;
                    }
                    if(vec[dx][dy]>='a'&&vec[dx][dy]<='z')
                    { 
                        x=x|(1<<(ch-'a')); //将该位变为1
                        if(x==((1<<k)-1))
                        { 
                            cout<<p.steps+1<<endl;
                            flag=true;
                            break;
                        }
                        que.push(Node(dx,dy,x,p.steps+1));
                        usr[dx][dy][x]=true;
                        
                    }
                    if(vec[dx][dy]>='A'&&vec[dx][dy]<='Z')
                    { 
                        int j=(ch+32-'a');
                        if(x>>j&1) //表示手中有匹配的钥匙
                        { 
                            que.push(Node(dx,dy,x,p.steps+1));
                            usr[dx][dy][x]=true;
                        }
                    }
                }
            }
        }
        if(flag==false) cout<<-1<<endl;
        return 0;
    }

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <vector>
    #include <string>
    #include <unordered_set>
    #include <queue>
    using namespace std;
    struct Step
    { 
        int x;
        int y;
        int ck; //目前手中钥匙的状态
        Step(int x, int y, int ck) : x(x), y(y), ck(ck) { }
    };
    class Solution
    { 
    public:
        queue<Step> que;
        bool vis[35][35][1 << 7] = { false}; //标记当前状态是否被拓展
        const int dis[4][2] = { 0, 1, 1, 0, 0, -1, -1, 0};
        int shortestPathAllKeys(vector<string> &grid)
        { 
            int len1 = grid.size();
            int len2 = grid[0].length();
            int k = 0; //记录钥匙的数量
            for (int i = 0; i < len1; i++)
            { 
                for (int j = 0; j < len2; j++)
                { 
                    if (grid[i][j] >= 'a' && grid[i][j] <= 'z')
                        k++;
                    if (grid[i][j] == '@')
                    { 
                        que.push(Step(i, j, 0));
                        vis[i][j][0] = true;
                    }
                }
            }
            int steps = 0;
            while (!que.empty())
            { 
                int l = que.size();
                while (l--)
                { 
                    Step u = que.front();
                    que.pop();
                    for (int i = 0; i < 4; i++)
                    { 
                        int dx = u.x + dis[i][0];
                        int dy = u.y + dis[i][1];
                        int x = u.ck; //取出当前状态
                        if (dx >= 0 && dx < len1 && dy >= 0 && dy < len2)
                        { 
                            char ch = grid[dx][dy];
                            if (ch == '#' || vis[dx][dy][x])
                                continue;
                            if (ch >= 'a' && ch <= 'z')
                            { 
                                x = x | (1 << (ch - 'a')); //将该位变为1
                                if (x == ((1 << k) - 1))
                                { 
                                    return steps + 1;
                                }
                            }
                            if (ch >= 'A' && ch <= 'Z' && !(x >> (ch - 'A') & 1))
                            { 
                                continue;
                            }
                            vis[dx][dy][x] = true;
                            que.push(Step(dx, dy, x));
                        }
                    }
                }
                steps++; //步数加1
            }
            return -1;
        }
    };
    vector<string> vec;
    int n, m;
    int main()
    { 
        //freopen("test.txt","r",stdin);
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        { 
            string ss;
            cin >> ss;
            vec.push_back(ss);
        }
        Solution s;
        cout << s.shortestPathAllKeys(vec) << endl;
        return 0;
    }

\#算法模版/状态压缩

[NCSTOJ-]: http://acm.ncst.edu.cn/contest_problem.php?cid=1025&pid=4
[LeetCode-864.]: https://leetcode-cn.com/problems/shortest-path-to-get-all-keys/