# C++ BFS pruning solution with comments beats 97.09% 6ms

• This solution is a basic BFS with two improvements.

• step1: for each 1, using queue<i, j> and global int visitedMap[i][j] to BFS and get distance to 0
update total distanceTable[i][j] in all 0s
update global int canVisitedMap[i][j] to count 1s that has visited 0s and 1s
Improvement 1: if current 0 is not accessible by previous 1s, skip it.
Improvement 2: if current 1 is not accessible by previous 1s, return -1
• step2: find shortest distance in all accessible 0s and return it
``````// time complexity: O(n^4), space complexity: O(n^2)
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
// get size
const int ROW_SIZE = grid.size();
const int COL_SIZE = grid[0].size();
// corner case
if (ROW_SIZE == 0 || COL_SIZE  == 0) {
return 0;
}
// visitedMap[i][j]: how many 1 could pass grid[i][j](0,1) from 1s [0->countBuilding-1]
// distanceTable[i][j]: total distance to grid[i][j] from 1s [0->countBuilding-1]
int countOne = 0;
vector<vector<int> > visitedMap(ROW_SIZE, vector<int>(COL_SIZE, 0));
vector<vector<int> > distanceTable(ROW_SIZE, vector<int>(COL_SIZE, 0));
// bfs from each 1 and get the distance to each 0, then add to distanceTable
// skip all 0s that some of buliding could not visit (countVisitedMap[i][j] < countBuilding)
for (int i = 0; i < ROW_SIZE; ++i) {
for (int j = 0; j < COL_SIZE; ++j) {
if (grid[i][j] == 1) {
if (!helperBFS(grid, i, j, distanceTable, visitedMap, countOne)) {
return -1;
}
countOne++;
}
}
}
// find the shortest distance in distanceTable
int shortestDistance = INT_MAX;
for (int i = 0; i < ROW_SIZE; ++i) {
for (int j = 0; j < COL_SIZE; ++j) {
if (distanceTable[i][j] > 0 && visitedMap[i][j] == countOne) {
shortestDistance = min(shortestDistance, distanceTable[i][j]);
}
}
}
return shortestDistance == INT_MAX ? -1 : shortestDistance;
}
private:
bool helperBFS(vector<vector<int> >& grid, int row, int col, vector<vector<int> >& distanceTable,
vector<vector<int> >& visitedMap, int countOne) {
// get size
const int ROW_SIZE = grid.size();
const int COL_SIZE = grid[0].size();
// use queue and visitedMap to bfs
queue<pair<int, int> > bfsQueue;
bfsQueue.push({row, col});
// bfs the shortest distance
int currDistance = 0;
while (!bfsQueue.empty()) {
int size = bfsQueue.size();
for (int i = 0; i < size; ++i) {
// visit current node and update the distance
pair<int, int> curr = bfsQueue.front();
bfsQueue.pop();
distanceTable[curr.first][curr.second] += currDistance;
// push all neighbor to the queue
int indexList[2][4] = {{-1, 0, 0, 1}, {0, -1, 1, 0}};
for (int j = 0; j < 4; j++) {
int x = curr.first + indexList[0][j], y = curr.second + indexList[1][j];
if (x >= 0 && x < ROW_SIZE && y >= 0 && y < COL_SIZE && visitedMap[x][y] != countOne + 1 && visitedMap[x][y] == countOne) {
if (grid[x][y] == 0) {
bfsQueue.push({x, y});
visitedMap[x][y]++;
} else if (grid[x][y] == 1) {
visitedMap[x][y]++;
}
}
}
}
currDistance++;
}
// if there is one 1 could not be accessed, return false
for (int i = 0; i < ROW_SIZE; ++i) {
for (int j = 0; j < COL_SIZE; ++j) {
if (grid[i][j] == 1 && visitedMap[i][j] != countOne + 1) {
return false;
}
}
}
return true;
}
};
``````

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