Đường đi ngắn nhất lấy tất cả chìa khóa trong C++

Cho lưới: '.' ô trống, '#' tường, '@' điểm bắt đầu, 'a'-'f' chìa khóa, 'A'-'F' khóa tương ứng. Di chuyển 4 hướng. Nhặt chìa khóa khi đi qua. Không thể qua khóa nếu chưa có chìa khóa. Tìm số bước tối thiểu lấy đủ chìa khóa, -1 nếu không thể.

Ví dụ: ["@.a.#","###.#","b.A.B"] → 8.

Giải pháp

BFS với trạng thái bitmask chìa khóa:

• Tìm start, đếm số loại chìa khóa (cnt), req = (1<
• Queue chứa {key_mask, x, y}, visited set các trạng thái
• BFS theo level:
  • Nếu key_mask == req: trả về level
  • Thử 4 hướng: nếu không phải tường
    • Nếu chìa khóa: key |= (1 << (ch-'a'))
    • Nếu khóa: kiểm tra bit tương ứng trong key, nếu 0 → bỏ qua
    • Trạng thái mới {new_key, nx, ny}, nếu chưa visited → push, mark visited
• Tăng level, lặp đến khi queue rỗng → -1

Ví dụ mã C++

#include <bits/stdc++.h> 
using namespace std; 

int dir[4][2] = {{1,0},{-1,0},{0,-1},{0,1}}; 

class Solution { 
public: 
    int shortestPathAllKeys(vector<string>& grid) { 
        int n = grid.size(); 
        int m = grid[0].size(); 
        vector<int> start(3); 
        int cnt = 0; 
        
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m; j++) { 
                if (grid[i][j] == '@') { 
                    start[1] = i; 
                    start[2] = j; 
                } 
                if (grid[i][j] >= 'a' && grid[i][j] <= 'f') 
                    cnt = max(cnt, grid[i][j] - 'a' + 1); 
            } 
        } 
        
        set<vector<int>> visited; 
        int req = (1 << cnt) - 1; 
        queue<vector<int>> q; 
        q.push(start); 
        visited.insert(start); 
        int level = 0; 
        
        while (!q.empty()) { 
            int sz = q.size(); 
            while (sz--) { 
                vector<int> curr = q.front(); q.pop(); 
                int key = curr[0]; 
                if (key == req) return level; 
                
                int x = curr[1], y = curr[2]; 
                int prevKey = key; 
                
                for (int i = 0; i < 4; i++) { 
                    int nx = x + dir[i][0]; 
                    int ny = y + dir[i][1]; 
                    key = prevKey; 
                    
                    if (nx >= 0 && ny >= 0 && nx < n && ny < m) { 
                        if (grid[nx][ny] == '#') continue; 
                        if (grid[nx][ny] >= 'a' && grid[nx][ny] <= 'f') 
                            key |= (1 << (grid[nx][ny] - 'a')); 
                        if (grid[nx][ny] >= 'A' && grid[nx][ny] <= 'F') 
                            if (((key >> (grid[nx][ny] - 'A')) & 1) == 0) 
                                continue; 
                        
                        vector<int> state = {key, nx, ny}; 
                        if (visited.count(state)) continue; 
                        q.push(state); 
                        visited.insert(state); 
                    } 
                } 
            } 
            level++; 
        } 
        return -1; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<string> v = {"@.a.#","###.#","b.A.B"}; 
    cout << (ob.shortestPathAllKeys(v)); 
    return 0; 
}

Đầu vào

{"@.a.#","###.#","b.A.B"}

Đầu ra

8