# BFS

• Since the problem asks for minimum steps, it is natural to think of BFS which guarantees shortest path. We can just try all moves starting from the initial board.

``````    int findMinStep(string board, string hand) {
unordered_map<char,int> ht;
for(char c:hand) ht[c]++;
queue<pair<string,unordered_map<char,int>>> q({make_pair(board,ht)});
int step = 0;
while(!q.empty()) {
int n = q.size();
step++;
for(int i=0;i<n;i++) {
auto& p = q.front();
string bd = p.first;
for(int j=0;j<bd.size();j++) {
auto hnd = p.second;
if(!hnd[bd[j]]) continue;
hnd[bd[j]]--;
string bod = bd;
int rmv = rm(bod.insert(j,1,bd[j]),j);
if(rmv) j+=rmv-1;
if(bod.empty()) return step;
q.push(make_pair(bod,hnd));
}
q.pop();
}
}
return -1;
}
int rm(string& board, int p) { //remove balls, return # of balls removed to the right of p
int l = p-1, r = p+1;
while(l>=0 && board[l]==board[p]) l--;
while(r<board.size()&& board[r]==board[p]) r++;
if(r-l>3) {
l++;
int rmv = rm(board.erase(l, r-l),l);
return r-p-1+rmv;
} else return 0;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.