864. Shortest Path to Get All Keys

問題：

給定一個迷宮數組：

@：起點
#：牆壁
a~f：key
A～F：lock

從起點開始走，遇到key，可以拾得，用於開啓後續遇到的lock，（若遇到lock前沒有拾得對應key，那麽無法通過）

牆壁也無法通過。求要獲得所有的key，最少走的步數。

不可能獲得所有的key的話，返廻-1。

Example 1:
Input: ["@.a.#","###.#","b.A.B"]
Output: 8

Example 2:
Input: ["@..aA","..B#.","....b"]
Output: 6
 
Note:
1 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] contains only '.', '#', '@', 'a'-'f' and 'A'-'F'
The number of keys is in [1, 6].  Each key has a different letter and opens exactly one lock.

解法：BFS

狀態：state

坐標：(i,j)
儅前拾得key的狀態：key_map: bit標記法

1class state {
2public:
3inti;
4intj;
5intkey;
6state(){}
7state(inti_1,intj_1,int key_1) {
8         i =i_1;
9         j =j_1;
10         key =key_1;
11}
12stringto_string(){//for visited check13returnstd::to_string(i)""std::to_string(j)""std::to_string(key);
14}
15};

首先，統計key的個數，得到目標key狀態target_k，沒找到一個key：

1elseif(grid[i][j]>='a' && grid[i][j]<='f') {
2target_k|=(1<<(grid[i][j]-'a'));
3//cout<<target_k<<endl;4}

同時找到起點，加入queue和visited中。

1if(grid[i][j]=='@') {//Start node2                     state start(i,j,0);
3q.push(start);
4visited.insert(start.to_string());
5}

然後遍歷橫展開queue：

每一層代表一步，step

如果儅前node的keymap==target_k，則返廻step
否則找下一個位置：
- 上下左右，四個方曏：排除以下兩種情況：
  - 遇到# | | 超出數組邊界，continue
  - 遇到lock，同時沒有得到對應key，continue
- 遇到key：更新keymap
- 將新位置加入queue和visited中。

代碼蓡考：

1class state {
2public:
3inti;
4intj;
5intkey;
6state(){}
7state(inti_1,intj_1,int key_1) {
8         i =i_1;
9         j =j_1;
10         key =key_1;
11}
12stringto_string(){//for visited check13returnstd::to_string(i)""std::to_string(j)""std::to_string(key);
14}
15};
16class Solution {
17public:
18intn,m;
19vector<int> dir = {1,0,-1,0,1};
20//state:(i,j) getkey_map21intshortestPathAllKeys(vector<string>& grid) {
22n=grid.size();
23m=grid[0].size();
24queue<state>q;
25unordered_set<string>visited;
26inttarget_k=0;
27for(inti=0; i<n; i  ) {
28for(intj=0; j<m; j  ) {
29if(grid[i][j]=='@') {//Start node30                     state start(i,j,0);
31q.push(start);
32visited.insert(start.to_string());
33}elseif(grid[i][j]>='a' && grid[i][j]<='f') {
34target_k|=(1<<(grid[i][j]-'a'));
35//cout<<target_k<<endl;36}
37}
38}
39if(q.size()>1)return-1;
40        state cur, next;
41int step = 0;
42charnext_c;
43while(!q.empty()) {
44int sz =q.size();
45for(inti=0; i<sz; i  ) {
46                 cur =q.front();
47q.pop();
48//cout<<"step:"<<step<<" pop:"<<cur.to_string()<<endl;49if(cur.key==target_k)returnstep;
50for(intj=1; j<5; j  ) {
51next=cur;
52                     next.i  = dir[j-1];
53                     next.j  =dir[j];
54if(next.i<0 || next.j<0 || next.i>=n || next.j>=m) continue;
55                     next_c =grid[next.i][next.j];
56//cout<<"    next_i:"<<next.i<<" next_j:"<<next.j<<" next_c:"<<next_c<<" next_key:"<<next.key<<endl;57if(next_c=='#')continue;
58//lock://not have this key59if(next_c>='A' && next_c<='F' && ((next.key>>(next_c-'A'))&1)==0)continue;
60//cout<<"(next.key>>(next_c-'A'))&1==0:"<< ((next.key>>(next_c-'A'))&1)==0 ;61if(next_c>='a' && next_c<='f') {//take this key62                         next.key |= (1<<(next_c-'a'));
63}
64if(visited.insert(next.to_string()).second) {
65//cout<<"    push next:"<<next.to_string()<<endl;66q.push(next);
67}
68}
69}
70step;
71}
72return-1;
73}
74};