problem:https://leetcode.com/problems/shortest-path-to-get-all-keys/
这道题其它地方都挺基础的,就是普通的宽搜,难点主要在于visit状态的维护。
如果不考虑visit数组,则会出现大量重复的来回搜索,比如刚刚从1->2,下一步又从2->1。
但是,已经访问过的地方,有可能再次被访问,比如先取得了钥匙a,因为前面没有路了,只能原路返回,再去取钥匙b。所以这意味着我们不能单独以坐标作为visit记录,而是需要考虑当前钥匙状态——没有拿到钥匙a和拿着钥匙a原路返回,这两者是存在差异的。前者是我们不期望的,后者则是我们需要重复搜索的(为了找到答案)。
class Solution { public: int m, n; vector<int> dx{ 0,1,0,-1 }; vector<int> dy{ 1,0,-1,0 }; bool checkKey(unsigned int key, char lock) { unsigned int data = lock - 'A'; return (key & (1 << data)) != 0; } int shortestPathAllKeys(vector<string>& grid) { m = grid.size(); n = grid[0].size(); queue<pair<int, unsigned int>> q; unsigned int target = 0; vector<vector<int>> visit(m * n, vector<int>(200,false)); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == '@') { visit[i * n + j][0] = true; q.push({ i * n + j, 0 }); } else if (grid[i][j] >= 'a' && grid[i][j] <= 'f') { target |= (1 << (grid[i][j] - 'a')); } } } int res = 0; while (!q.empty()) { int size = q.size(); res++; while (size--) { auto cur = q.front(); q.pop(); int i = cur.first / n; int j = cur.first % n; unsigned int key = cur.second; for (int k = 0; k < 4; k++) { int x = i + dx[k]; int y = j + dy[k]; if (x >= 0 && y >= 0 && x < m && y < n) { if(grid[x][y] == '#') continue; int next = x * n + y; int newKey = key; if (grid[x][y] >= 'A' && grid[x][y] <= 'F') { if (!checkKey(key, grid[x][y])) { continue; } } else if (grid[x][y] >= 'a' && grid[x][y] <= 'f') { newKey = key | (1 << (grid[x][y] - 'a')); if (newKey == target) { return res; } } if(!visit[next][newKey]) { visit[next][newKey] = true; q.push({next, newKey}); } } } } } return -1; } };