Maze I
bool hasPath(vector<vector<int>> & maze, vector<int> & start, vector<int> & dest) {
const vector<int> dx = {0, -1, 1, 0};
const vector<int> dy = {1, 0, 0, -1};
queue<pair<int, int>> q;
q.emplace(start[0], start[1]);
maze[start[0]][start[1]] = 2;
int m = maze.size();
int n = maze.front().size();
while (!q.empty()) {
auto cur = q.front();
q.pop();
int x = cur.first;
int y = cur.second;
if (x == dest[0] && y == dest[1]) {
return true;
}
for (int i = 0; i < 4; i++) {
int xx = x;
int yy = y;
while (xx >= 0 && xx < m && yy >= 0 && yy < n && maze[xx][yy] != 1) {
xx += dx[i];
yy += dy[i];
}
xx -= dx[i];
yy -= dy[i];
if (maze[xx][yy] == 0) {
maze[xx][yy] = 2;
q.emplace(xx, yy);
}
}
}
return false;
}
Maze II
struct Position {
int x, y, d;
Position(int x, int y, int d): x(x), y(y), d(d) {}
};
class Solution {
public:
int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& dest) {
if (maze.empty()) {
return -1;
}
auto cmp = [](Position & p1, Position & p2) {return p1.d > p2.d;};
priority_queue<Position, vector<Position>, decltype(cmp)> pq(cmp);
pq.emplace(Position(start[0], start[1], 0));
int m = maze.size();
int n = maze.front().size();
vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
const vector<int> dx = {0, 1, -1, 0};
const vector<int> dy = {1, 0, 0, -1};
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
int x = p.x;
int y = p.y;
int d = p.d;
if (x == dest[0] && y == dest[1]) {
return d;
}
dis[x][y] = d;
for (int i = 0; i < 4; i++) {
int nx = x;
int ny = y;
int nd = d;
while (nx + dx[i] < m && nx + dx[i] >= 0 && ny + dy[i] < n && ny + dy[i] >= 0
&& maze[nx + dx[i]][ny + dy[i]] == 0) {
nx += dx[i];
ny += dy[i];
nd++;
}
if (dis[nx][ny] > nd) {
dis[nx][ny] = nd;
pq.emplace(Position(nx, ny, nd));
}
}
}
return -1;
}
};
Maze III
struct State
{
int x;
int y;
int d;
State (int x, int y, int d) : x(x), y(y), d(d) {}
};
const vector<int> dx = {1, -1, 0, 0};
const vector<int> dy = {0, 0, -1, 1};
const string dirs = "dulr";
class Solution {
public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
auto cmp = [](State & s1, State & s2) {
return s1.d > s2.d;
};
priority_queue<State, vector<State>, decltype(cmp)> pq(cmp);
pq.emplace(ball[0], ball[1], 0);
int m = maze.size();
int n = maze.front().size();
//dis[x][y]=>maintain the shortest distance to the source so far
vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
//dir[x][y]=>maintain the lexicographically smallest way from the source so far
vector<vector<string>> way(m, vector<string>(n));
while(!pq.empty()) {
auto state = pq.top();
pq.pop();
int x = state.x;
int y = state.y;
int d = state.d;
if (d > dis[x][y]) {
continue;
}
string path = way[x][y];
dis[x][y] = d;
if (x == hole[0] && y == hole[1]) {
return way[x][y];
}
for (int i = 0; i < 4; i++) {
int nx = x;
int ny = y;
int nd = d;
string path = way[x][y] + dirs[i];
while (nx + dx[i] < m && nx + dx[i] >= 0 && ny + dy[i] < n && ny + dy[i] >= 0
&& maze[nx + dx[i]][ny + dy[i]] == 0) {
nx += dx[i];
ny += dy[i];
nd++;
if (nx == hole[0] && ny == hole[1]) {
break;
}
}
if (nd < dis[nx][ny]) {
dis[nx][ny] = nd;
way[nx][ny] = path;
pq.emplace(nx, ny, nd);
}
if (nd == dis[nx][ny]) {
if (path < way[nx][ny]) {
way[nx][ny] = path;
}
}
}
}
return "impossible";
}
};
Leetcode 317: Shortest Distance from All Buildings
找到一个点，从他开始到所有的buildings的距离最短的和，中间有障碍物。对每个点做BFS，然后加起来求一个最小值。这样的时间复杂度是 $O(m*n)[BFS] * O(m*n)[matrix] = O(m^2*n^2)$。优化：从building开始搜。那么时间复杂度为$O(k*m*n)$。 $k$ 是 building 的个数。
class Solution {
public:
int shortestDistance(vector<vector<int>>& grid) {
int res = INT_MAX;
vector<vector<pair<int, int>>> dis(grid.size(), vector<pair<int, int>>(grid[0].size()));
//dis[i][j].first => total distance from k buildings to grid[i][j]
//dis[i][j].second => num of times search from k buildings and visited to grid[i][j] successfully (avoid dead end)
int m = grid.size();
int n = grid[0].size();
int num_buildings = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
bfs(grid, dis, i, j);
num_buildings++;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (dis[i][j].second == num_buildings) {
res = min(res, dis[i][j].first);
}
}
}
return res == INT_MAX? -1 : res;
}
void bfs(const vector<vector<int>> & grid, vector<vector<pair<int, int>>> & dis, int i, int j) {
queue<pair<int, int>> q;
q.emplace(i, j);
int m = grid.size();
int n = grid[0].size();
deque<deque<bool>> visited(m, deque<bool>(n, false));
vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int level = 0; //distance to building in grid[i][j]
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (level != 0) {
dis[x][y].first += level;
dis[x][y].second++;
}
for (const auto & dir : dirs) {
int x_prime = x + dir.first;
int y_prime = y + dir.second;
if (x_prime < m && x_prime >= 0 && y_prime < n && y_prime >= 0 &&
grid[x_prime][y_prime] == 0 &&
visited[x_prime][y_prime] == false) {
q.emplace(x_prime, y_prime);
visited[x_prime][y_prime] = true;
}
}
}
level++;
}
}
};
Best Meeting Point
和上题一样的做法，只是可以在人所在的位置。做BFS标记visited的时候要注意。
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
int res = INT_MAX;
vector<vector<int>> dis(grid.size(), vector<int>(grid[0].size()));
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 1) {
bfs(grid, dis, i, j);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res = min(res, dis[i][j]);
}
}
return res == INT_MAX? -1 : res;
}
void bfs(const vector<vector<int>> & grid, vector<vector<int>> & dis, int i, int j) {
queue<pair<int, int>> q;
q.emplace(i, j);
int m = grid.size();
int n = grid[0].size();
deque<deque<bool>> visited(m, deque<bool>(n, false));
visited[i][j] = true;
vector<pair<int, int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int level = 0; //distance to grid[i][j]
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int x = q.front().first;
int y = q.front().second;
q.pop();
if (level != 0) {
dis[x][y] += level;
}
for (const auto & dir : dirs) {
int x_prime = x + dir.first;
int y_prime = y + dir.second;
if (x_prime < m && x_prime >= 0 && y_prime < n && y_prime >= 0 &&
visited[x_prime][y_prime] == false) {
q.emplace(x_prime, y_prime);
visited[x_prime][y_prime] = true;
}
}
}
level++;
}
}
};
但超时啦。 答案里给的方法是算出median。并不适用有obstacle的情况（是嘛？）。
// Time: O(mn)
// Space: O(m+n)
class Solution {
public:
int minTotalDistance(vector<vector<int>>& grid) {
vector<int> x, y;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j]) {
x.emplace_back(i);
y.emplace_back(j);
}
}
}
nth_element(x.begin(), x.begin() + x.size() / 2, x.end());
nth_element(y.begin(), y.begin() + y.size() / 2, y.end());
const int mid_x = x[x.size() / 2];
const int mid_y = y[y.size() / 2];
int sum = 0;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[0].size(); ++j) {
if (grid[i][j]) {
sum += abs(mid_x - i) + abs(mid_y - j);
}
}
}
return sum;
}
};
- nth_element() 把按 comparator 排序的有第n个数放在 n 的位置，前面的都比它“小”， 后面的都比它“大”。 但其他并不保证有序，时间复杂度 $O(n)$ 比 sort 好一些。
Dijkstra
https://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-set-in-stl/
https://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/
A star
https://github.com/pineal/-O_O-/blob/master/A_Star_Search/A_Star_Search.cpp