# C++ Simple Solution, Concise Code

• bfs

``````class Solution {
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
int m = maze.size(), n = m ? maze[0].size() : 0;
pair<int, int> end = {destination[0], destination[1]};
vector<vector<int>> dis(m, vector<int>(n , -1));
vector<pair<int, int>> neis = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
queue<pair<int, int>> qu;
qu.push({start[0], start[1]});
dis[start[0]][start[1]] = 0;

while (qu.size()) {
int r = qu.front().first, c = qu.front().second;
qu.pop();

for (auto nei : neis) {
int row = r, col = c, move = 0;
while (row + nei.first >= 0 && row + nei.first < m
&& col + nei.second >= 0 && col + nei.second < n && maze[row + nei.first][col + nei.second] != 1) {
row += nei.first;
col += nei.second;
move++;
}
if (dis[row][col] == -1 || dis[row][col] > move + dis[r][c]) {
qu.push({row, col});
dis[row][col] = move + dis[r][c];
}
}
}
return dis[destination[0]][destination[1]];
}
};
``````

bfs by steps

``````class Solution {
bool isWall(vector<vector<int>>& maze, int r, int c) {
int m = maze.size(), n = maze[0].size();
if (r < 0 || r >= m || c < 0 || c >= n || maze[r][c] == 1)
return true;
return false;
}

int intValueOfDirection(pair<int, int> direction) {
if (direction.first == 0) {
if (direction.second == 1) {
return 0;
} else {
return 1;
}
} else {
if (direction.second == 1) {
return 2;
} else {
return 3;
}
}
return -1;
}
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {

queue<pair<int, int>> st_point;
queue<pair<int, int>> st_direction;
queue<int> st_dis;
unordered_map<int, unordered_map<int, unordered_map<int, int>>> mp;

vector<pair<int, int>> neis = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
pair<int, int> end = {destination[0], destination[1]};

for (auto nei : neis) {
st_point.push({start[0], start[1]});
st_direction.push(nei);
st_dis.push(0);
}

while (st_dis.size()) {
pair<int, int> point = st_point.front(), direction = st_direction.front();
int dis = st_dis.front();
st_point.pop();
st_direction.pop();
st_dis.pop();

if (isWall(maze, point.first, point.second) || (mp[point.first][point.second].find(intValueOfDirection(direction)) != mp[point.first][point.second].end() && mp[point.first][point.second][intValueOfDirection(direction)] < dis))
continue;
mp[point.first][point.second][intValueOfDirection(direction)] = dis;
if (isWall(maze, point.first + direction.first, point.second + direction.second)) {
//
if (point == end)
return dis;
for (auto nei : neis) {
st_point.push({point.first + nei.first, point.second + nei.second});
st_direction.push(nei);
st_dis.push(dis + 1);
}
} else {
st_point.push({point.first + direction.first, point.second + direction.second});
st_direction.push(direction);
st_dis.push(dis + 1);
}

}

return -1;
}
};
``````

dfs

``````class Solution {
void dfs(vector<vector<int>>& maze, vector<vector<int>>& dis, int row, int col) {
int m = maze.size(), n = m ? maze[0].size() : 0;
vector<pair<int, int>> neis = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (auto nei : neis) {
int r = row, c = col, move = 0;
while (r + nei.first >= 0 && r + nei.first < m && c + nei.second >= 0 && c + nei.second < n && maze[r + nei.first][c + nei.second] != 1) {
r += nei.first;
c += nei.second;
move++;
}
if (dis[r][c] == -1 || dis[r][c] > dis[row][col] + move) {
dis[r][c] = dis[row][col] + move;
dfs(maze, dis, r, c);
}
}
}
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
int m = maze.size(), n = m ? maze[0].size() : 0;
vector<vector<int>> dis(m, vector<int>(n, -1));
dis[start[0]][start[1]] = 0;

dfs(maze, dis, start[0], start[1]);

return dis[destination[0]][destination[1]];
}
};
``````

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