|
问题： 给定一个迷宫数组：
从起点开始走，遇到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
1 class state { 2 public: 3 int i; 4 int j; 5 int key; 6 state(){} 7 state(int i_1, int j_1, int key_1) { 8 i = i_1; 9 j = j_1; 10 key = key_1; 11 } 12 string to_string(){//for visited check 13 return std::to_string(i) + " " + std::to_string(j) + " " + std::to_string(key); 14 } 15 };
首先，统计key的个数，得到目标key状态target_k，没找到一个key： 1 else if(grid[i][j]>='a' && grid[i][j]<='f') { 2 target_k|=(1<<(grid[i][j]-'a')); 3 //cout<<target_k<<endl; 4 }
同时找到起点，加入queue和visited中。 1 if(grid[i][j]=='@') {//Start node 2 state start(i,j,0); 3 q.push(start); 4 visited.insert(start.to_string()); 5 }
然后遍历横展开queue： 每一层代表一步，step++
代码参考： 1 class state { 2 public: 3 int i; 4 int j; 5 int key; 6 state(){} 7 state(int i_1, int j_1, int key_1) { 8 i = i_1; 9 j = j_1; 10 key = key_1; 11 } 12 string to_string(){//for visited check 13 return std::to_string(i) + " " + std::to_string(j) + " " + std::to_string(key); 14 } 15 }; 16 class Solution { 17 public: 18 int n,m; 19 vector<int> dir = {1,0,-1,0,1}; 20 //state:(i,j) getkey_map 21 int shortestPathAllKeys(vector<string>& grid) { 22 n=grid.size(); 23 m=grid[0].size(); 24 queue<state> q; 25 unordered_set<string> visited; 26 int target_k=0; 27 for(int i=0; i<n; i++) { 28 for(int j=0; j<m; j++) { 29 if(grid[i][j]=='@') {//Start node 30 state start(i,j,0); 31 q.push(start); 32 visited.insert(start.to_string()); 33 } else if(grid[i][j]>='a' && grid[i][j]<='f') { 34 target_k|=(1<<(grid[i][j]-'a')); 35 //cout<<target_k<<endl; 36 } 37 } 38 } 39 if(q.size()>1) return -1; 40 state cur, next; 41 int step = 0; 42 char next_c; 43 while(!q.empty()) { 44 int sz = q.size(); 45 for(int i=0; i<sz; i++) { 46 cur = q.front(); 47 q.pop(); 48 //cout<<"step:"<<step<<" pop:"<<cur.to_string()<<endl; 49 if(cur.key==target_k) return step; 50 for(int j=1; j<5; j++) { 51 next = cur; 52 next.i += dir[j-1]; 53 next.j += dir[j]; 54 if(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; 57 if(next_c=='#') continue; 58 //lock://not have this key 59 if(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 ; 61 if(next_c>='a' && next_c<='f') {//take this key 62 next.key |= (1<<(next_c-'a')); 63 } 64 if(visited.insert(next.to_string()).second) { 65 //cout<<" push next:"<<next.to_string()<<endl; 66 q.push(next); 67 } 68 } 69 } 70 step++; 71 } 72 return -1; 73 } 74 };
⚠️ 注意：两层if嵌套的时候，内层continue，无法使得外层也continue。 |
|
|
