# C++ BFS solution

• BFS can tell us which position can be arrived.
When we do the BFS, we update the distance at the same time.
If other paths give us shorter distance, we visit that position one more time.

``````class Solution {
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
int rows=(int)maze.size();
int cols=(int)maze[0].size();
vector<vector<int>> maze_2 (rows, vector<int> (cols, 0));

for(int i=0; i<rows; i++) {
for(int j=0; j<cols; j++) {
if(maze[i][j]==1)
maze_2[i][j]=-1;
else
maze_2[i][j]=INT_MAX;
}
}

queue<vector<int>> my_queue;
my_queue.push(start);
maze_2[start[0]][start[1]]=0;

while(my_queue.size()!=0) {
vector<int> now=my_queue.front();
my_queue.pop();

int dis=maze_2[now[0]][now[1]];

// up
int tr=now[0];
int tc=now[1];
int step=0;
while(tr>0 && maze[tr-1][tc]!=1) {
tr--;
step++;
}
if(dis+step<maze_2[tr][tc]) {
maze_2[tr][tc]=dis+step;
my_queue.push({tr, tc});
}

// down
tr=now[0]; tc=now[1]; step=0;
while(tr<rows-1 && maze[tr+1][tc]!=1) {
tr++;
step++;
}
if(dis+step<maze_2[tr][tc]) {
maze_2[tr][tc]=dis+step;
my_queue.push({tr, tc});
}

// left
tr=now[0]; tc=now[1]; step=0;
while(tc>0 && maze[tr][tc-1]!=1) {
tc--;
step++;
}
if(dis+step<maze_2[tr][tc]) {
maze_2[tr][tc]=dis+step;
my_queue.push({tr, tc});
}

// right
tr=now[0]; tc=now[1]; step=0;
while(tc<cols-1 && maze[tr][tc+1]!=1) {
tc++;
step++;
}
if(dis+step<maze_2[tr][tc]) {
maze_2[tr][tc]=dis+step;
my_queue.push({tr, tc});
}
}

if(maze_2[destination[0]][destination[1]]==INT_MAX)
return -1;
return maze_2[destination[0]][destination[1]];
}
};``````

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