เส้นทางสั้นที่สุดเก็บกุญแจครบทุกประตูใน C++

คำอธิบายโจทย์

กริด: '.'=ว่าง, '#'=กำแพง, '@'=เริ่ม, 'a'-'f'=กุญแจ, 'A'-'F'=ประตู (ต้องมีกุญแจตรงตัวพิมพ์เล็ก) เดิน 4 ทิศทาง หา steps น้อยสุดเก็บกุญแจครบ ไม่ได้คืน -1

ตัวอย่าง

grid = ["@.a.#","###.#","b.A.B"] → Output: 8

วิธีแก้ปัญหา

BFS + Bitmask State:

• State: (x, y, keys_bitmask) keys_bitmask: bit i=1 ถ้ามีกุญแจ 'a'+i
• Visited: set ของ (x,y,keys)
• เริ่มจาก '@' keys=0
• เดิน 4 ทิศทาง: ผ่านกำแพงไม่ได้, เจอกุญแจ → set bit, เจอประตู → check bit
• ถึง keys == all_keys_mask → คืน level

การทำงานของโค้ด

#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(), m=grid[0].size();
        vector<int> start(3);
        int cnt=0;
        
        for(int i=0;i='a' && grid[i][j]<='f') 
                cnt = max(cnt, grid[i][j]-'a'+1);
        }
        
        set<vector<int>> visited;
        int req = (1<=n||ny>=m) continue;
                    if(grid[nx][ny]=='#') continue;
                    if(grid[nx][ny]>='a' && grid[nx][ny]<='f')
                        nkey |= (1<<(grid[nx][ny]-'a'));
                    if(grid[nx][ny]>='A' && grid[nx][ny]<='F')
                        if(!((key>>(grid[nx][ny]-'A'))&1)) continue;
                    
                    vector<int> state = {nkey, nx, ny};
                    if(visited.count(state)) continue;
                    visited.insert(state);
                    q.push(state);
                }
            }
            level++;
        }
        return -1;
    }
};

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

อินพุต

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

เอาต์พุต

8