Hard Graph problems
5 min readJul 18, 2020
Problems
847. Shortest Path Visiting All Nodes
980. Unique Paths III
864. Shortest Path to Get All Keys
see[1]
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
