# Problems

## Naive BFS solution got TLE

`class Solution {public:    int shortestPathAllKeys(vector<string>& grid) {        const int R = grid.size(), C = grid[0].size();        int sr, sc;        set<char> keys;        for(int i=0;i<R;++i)            for(int j=0;j<C;++j)            {                if(grid[i][j]=='@')                {                    sr = i, sc = j;                }                if(grid[i][j]>='a' && grid[i][j]<='f')                {                    keys.insert(grid[i][j]);                }            }        // i, j, cost, key1, key2,...        queue<vector<int>> Q;        Q.push(vector<int>{sr, sc, 0});        set<vector<int>> seen;        seen.insert({sr, sc});        vector<pair<int, int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};        while(!Q.empty())        {            auto state = Q.front();            Q.pop();            auto i = state[0], j=state[1], cost = state[2];            if(state.size()==3+keys.size())return cost;                        vector<int> this_state, this_q_state;            for(auto [di, dj]: dirs)            {                auto r = i+di, c = j+dj;                if(r<0 || r>=R || c<0||c>=C || grid[r][c]=='#')continue;                vector<int> new_state = {r, c};                if (grid[r][c]>='a' && grid[r][c]<='f')                {                    this_state = new_state;                    this_q_state = new_state;                    this_q_state.push_back(cost+1);                    bool has_key = false;                    for(int k=3;k<state.size();++k)                    {                        if(state[k]==int(grid[r][c]))has_key=true;                        this_state.push_back(state[k]);                        this_q_state.push_back(state[k]);                    }                    if (not has_key)                    {                        this_state.push_back(grid[r][c]);                        sort(this_state.begin()+2, this_state.end());                        this_q_state.push_back(grid[r][c]);                    }                    if(seen.find(this_state)==seen.end())                    {                        seen.insert(this_state);                        Q.push(this_q_state);                    }                }                else if(grid[r][c]>='A' && grid[r][c]<='F')                {                    if(find(state.begin()+3, state.end(), int(tolower(grid[r][c])))==state.end())                        continue;                    this_state = new_state;                    this_q_state = {r, c};                    this_q_state.push_back(cost+1);                    for(int k=3;k<state.size();++k)                    {                        this_state.push_back(state[k]);                        this_q_state.push_back(state[k]);                    }                    if(seen.find(this_state)==seen.end())                    {                        seen.insert(this_state);                        Q.push(this_q_state);                    }                    }                else if(grid[r][c]>='.' || grid[r][c]<='@')                {                    this_state = new_state;                    this_q_state = new_state;                    this_q_state.push_back(cost+1);                    for(int k=3;k<state.size();++k)                    {                        this_state.push_back(state[k]);                        this_q_state.push_back(state[k]);                    }                    if(seen.find(this_state)==seen.end())                    {                        seen.insert(this_state);                        Q.push(this_q_state);                    }                }            }        }        return -1;    }};`

Using bitmask to represent the state of the keys can get AC (1600ms+)

`class Solution {public:    int shortestPathAllKeys(vector<string>& grid) {        const int R = grid.size(), C = grid[0].size();        int sr, sc;        int keys=0;        for(int i=0;i<R;++i)            for(int j=0;j<C;++j)            {                if(grid[i][j]=='@')                {                    sr = i, sc = j;                }                if(grid[i][j]>='a' && grid[i][j]<='f')                {                    keys++;                }            }        // i, j, cost, keys        queue<vector<int>> Q;        Q.push(vector<int>{sr, sc, 0, 0});        set<vector<int>> seen;        seen.insert({sr, sc, 0});        vector<pair<int, int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};        while(!Q.empty())        {            auto state = Q.front();            Q.pop();            auto i = state[0], j=state[1], cost = state[2], this_keys=state[3];            vector<int> this_state, this_q_state;            for(auto [di, dj]: dirs)            {                auto r = i+di, c = j+dj;                if(r<0 || r>=R || c<0||c>=C || grid[r][c]=='#')continue;                if (grid[r][c]>='a' && grid[r][c]<='f')                {                    auto new_keys = this_keys | (1<<(grid[r][c]-'a'));                    if(__builtin_popcount(new_keys)==keys)return cost+1;                    this_state = {r, c, new_keys};                        this_q_state = {r, c, cost+1, new_keys};                    if(seen.find(this_state)==seen.end())                    {                                                seen.insert(this_state);                        Q.push(this_q_state);                    }                }                else if(grid[r][c]>='A' && grid[r][c]<='F')                {                    if(!(this_keys&(1<<(grid[r][c]-'A'))))                        continue;                    this_state = {r, c, this_keys};                    this_q_state = {r, c, cost+1, this_keys};                    if(seen.find(this_state)==seen.end())                    {                        seen.insert(this_state);                        Q.push(this_q_state);                    }                    }                else if(grid[r][c]>='.' || grid[r][c]<='@')                {                    this_state = {r, c, this_keys};                    this_q_state = {r, c, cost+1, this_keys};                    if(seen.find(this_state)==seen.end())                    {                        seen.insert(this_state);                        Q.push(this_q_state);                    }                }            }        }        return -1;    }};`

A more concise way by using a standard BFS template (1600ms+)

`class Solution {public:    int shortestPathAllKeys(vector<string>& grid) {        const int R = grid.size(), C = grid[0].size();        int sr, sc;        int keys=0;        for(int i=0;i<R;++i)            for(int j=0;j<C;++j)            {                if(grid[i][j]=='@')                {                    sr = i, sc = j;                }                if(grid[i][j]>='a' && grid[i][j]<='f')                {                    keys |= (1<<(grid[i][j]-'a'));                }            }        // i, j, keys        queue<vector<int>> Q;        Q.push(vector<int>{sr, sc, 0});        set<vector<int>> seen;        seen.insert({sr, sc, 0});        vector<pair<int, int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};        int step = 0;        while(!Q.empty())        {            int len = Q.size();            while(len--)            {                //ut<<len<<endl;                auto state = Q.front(); Q.pop();                auto i = state[0], j=state[1], this_keys=state[2];                if (this_keys==keys)return step;                for(auto [di, dj]: dirs)                {                    auto r = i+di, c = j+dj;                    //ut<<"rc"<<r<<" "<<c<<endl;                    if(r<0 || r>=R || c<0||c>=C || grid[r][c]=='#')continue;                    auto new_keys = this_keys;                    if (grid[r][c]>='a' && grid[r][c]<='f')new_keys |= (1<<(grid[r][c]-'a'));                    if (grid[r][c]>='A' && grid[r][c]<='F' && !(new_keys&(1<<(grid[r][c]-'A'))))continue;                       vector<int> new_state ={r, c, new_keys};                    if(seen.find(new_state)==seen.end())                    {                        seen.insert(new_state);                        Q.push(new_state);                    }                    }            }            ++step;        }        return -1;    }};`

Using a 3D vector for seen can significantly reduce the execution time to about 340 ms.

`class Solution {public:    int shortestPathAllKeys(vector<string>& grid) {        const int R = grid.size(), C = grid[0].size();        int keys=0;         // i,  j, keys        queue<vector<int>> Q;        vector<vector<vector<int>>> seen(R, vector<vector<int>>(C, vector<int>(64, 0)));        for(int i=0;i<R;++i)            for(int j=0;j<C;++j)            {                if(grid[i][j]=='@')                {                    Q.push(vector<int>{i,j, 0});                    seen[i][j][0] = 1;}                if(grid[i][j]>='a' && grid[i][j]<='f')                {                    keys |= (1<<(grid[i][j]-'a'));                }            }                vector<pair<int, int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};        int step = 0;        while(!Q.empty())        {            int len = Q.size();            while(len--)            {                auto state = Q.front(); Q.pop();                auto i = state[0], j=state[1], this_keys=state[2];                if (this_keys==keys)return step;                for(auto [di, dj]: dirs)                {                    auto r = i+di, c = j+dj;                    if(r<0 || r>=R || c<0||c>=C || grid[r][c]=='#')continue;                    auto new_keys = this_keys;                    if (grid[r][c]>='a' && grid[r][c]<='f')new_keys |= (1<<(grid[r][c]-'a'));                    if (grid[r][c]>='A' && grid[r][c]<='F' && !(new_keys&(1<<(grid[r][c]-'A'))))continue;                       vector<int> new_state ={r, c, new_keys};                    if(seen[r][c][new_keys]==0)                    {                        seen[r][c][new_keys] = 1;                        Q.push(new_state);                    }                    }            }            ++step;        }        return -1;    }};`

Using a node to store all the information needed can further reduce the running time to less than 100 ms.

`class node{ public:    int i, j, this_keys;};class Solution {public:    int shortestPathAllKeys(vector<string>& grid) {        const int R = grid.size(), C = grid[0].size();        int keys=0;        queue<node> Q;        int seen[31][31][65];        memset(seen, 0, sizeof seen);        for(int i=0;i<R;++i)            for(int j=0;j<C;++j)            {                if(grid[i][j]=='@')                {                    Q.push({i,j, 0});                    seen[i][j][0] = 1;}                if(grid[i][j]>='a' && grid[i][j]<='f')                {                    keys |= (1<<(grid[i][j]-'a'));                }            }                vector<pair<int, int>> dirs = {{1,0},{0, 1},{0,-1},{-1, 0}};        int step = 0;        while(!Q.empty())        {            int len = Q.size();            while(len--)            {                //ut<<len<<endl;                auto state = Q.front(); Q.pop();                auto i = state.i,                     j=state.j,                      this_keys=state.this_keys;                if (this_keys==keys)return step;                for(auto& [di, dj]: dirs)                {                    auto r = i+di, c = j+dj;                    //ut<<"rc"<<r<<" "<<c<<endl;                    if(r<0 || r>=R || c<0||c>=C || grid[r][c]=='#')continue;                    auto new_keys = this_keys;                    if (grid[r][c]>='a' && grid[r][c]<='f')new_keys |= (1<<(grid[r][c]-'a'));                    if (grid[r][c]>='A' && grid[r][c]<='F' && !(new_keys&(1<<(grid[r][c]-'A'))))continue;                       if(seen[r][c][new_keys]==0)                    {                        seen[r][c][new_keys] = 1;                        Q.push({r, c, new_keys});                    }                    }            }            ++step;        }        return -1;    }};`

We can also use pair (40 ms).

`typedef pair<int, int> ii;typedef vector<ii> vii;class Solution {public:    int shortestPathAllKeys(vector<string>& grid) {        const int R = grid.size(), C = grid[0].size();        int keys=0;        queue<ii> Q;        int seen[31][31][65];        memset(seen, 0, sizeof seen);        for(int i=0;i<R;++i)            for(int j=0;j<C;++j)            {                if(grid[i][j]=='@')                {                    Q.emplace(i*C + j, 0);                    seen[i][j][0] = 1;                }                if(grid[i][j]>='a' && grid[i][j]<='f')                {                    keys |= (1<<(grid[i][j]-'a'));                }            }                vii dirs = {{1,0},{0, 1},{0,-1},{-1, 0}};        int step = 0;        while(!Q.empty())        {            int len = Q.size();            while(len--)            {                //ut<<len<<endl;                auto [idx, this_keys] = Q.front(); Q.pop();                auto i = idx/C, j = idx%C;                if (this_keys==keys)return step;                for(auto& [di, dj]: dirs)                {                    auto r = i+di, c = j+dj;                    if(r<0 || r>=R || c<0||c>=C || grid[r][c]=='#')continue;                    auto new_keys = this_keys;                    if (grid[r][c]>='a' && grid[r][c]<='f')new_keys |= (1<<(grid[r][c]-'a'));                    if (grid[r][c]>='A' && grid[r][c]<='F' && !(new_keys&(1<<(grid[r][c]-'A'))))continue;                       if(seen[r][c][new_keys]==0)                    {                        seen[r][c][new_keys] = 1;                        Q.emplace(r*C + c, new_keys);                    }                    }            }            ++step;        }        return -1;    }};`

787. Cheapest Flights Within K Stops

# Reference

Data Scientist/MLE/SWE @takemobi

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi