题目
思路
- 直接BFS——按照树高排序，转换成多个最短路径叠加问题，其中引入visited数组，保存已经访问过的节点。
- Dijkstra算法——在BFS时候，引入优先队列，优先队列维护已用步数最少的路径方法。
- A* 启发式搜索算法——在BFS时候，维护剩余曼哈顿距离最小的点，得到最终结果。
实现
class Solution {
public:
int len_m;
int len_n;
vector> edges;
const int direction[5] = { 1, 0, -1, 0, 1 };
int cutOffTree(vector>& forest) {
edges = forest;
len_m = edges.size();
len_n = edges[0].size();
int ret = 0;
vector> pos_vec;
for (int i = 0; i < len_m; ++i) {
for (int j = 0; j < len_n; ++j) {
if (edges[i][j] > 1)
pos_vec.emplace_back(edges[i][j], i * len_n + j);
}
}
sort(pos_vec.begin(), pos_vec.end());
int len = pos_vec.size();
int pre = 0;
for (int i = 0; i < len; ++i) {
int temp = bfs(pre, pos_vec[i].second);
if (temp == -1)
return -1;
ret += temp;
pre = pos_vec[i].second;
}
return ret;
}
int bfs(int start, int end) {
if (start == end)
return 0;
int step = 1;
queue que;
vector> visited(len_m, vector(len_n));
que.emplace(start);
visited[start / len_n][start % len_n] = true;
int nums = 1;
while (!que.empty()) {
nums--;
auto front = que.front();
que.pop();
for (int i = 0; i < 4; ++i) {
int new_x = front / len_n + direction[i];
int new_y = front % len_n + direction[i + 1];
if (new_x >= 0 && new_x < len_m && new_y >= 0 && new_y < len_n &&
!visited[new_x][new_y] && edges[new_x][new_y] > 0) {
if (new_x * len_n + new_y == end) {
return step;
}
que.emplace(new_x * len_n + new_y);
visited[new_x][new_y] = true;
}
}
if (nums == 0) {
nums = que.size();
step++;
}
}
return -1;
}
};
class Solution {
public:
int len_m;
int len_n;
vector> edges;
const int direction[5] = { 1, 0, -1, 0, 1 };
int cutOffTree(vector>& forest) {
edges = forest;
len_m = edges.size();
len_n = edges[0].size();
int ret = 0;
vector> pos_vec;
for (int i = 0; i < len_m; ++i) {
for (int j = 0; j < len_n; ++j) {
if (edges[i][j] > 1)
pos_vec.emplace_back(edges[i][j], i * len_n + j);
}
}
sort(pos_vec.begin(), pos_vec.end());
int len = pos_vec.size();
int pre = 0;
for (int i = 0; i < len; ++i) {
int temp = bfs(pre, pos_vec[i].second);
if (temp == -1)
return -1;
ret += temp;
pre = pos_vec[i].second;
}
return ret;
}
int bfs(int start, int end) {
if (start == end)
return 0;
int step = 1;
priority_queue, vector>, greater>> prio_que;
vector> visited(len_m, vector(len_n));
prio_que.emplace(0, start);
visited[start / len_n][start % len_n] = true;
while (!prio_que.empty()) {
auto front = prio_que.top();
prio_que.pop();
int dist = front.first;
int loc = front.second;
for (int i = 0; i < 4; ++i) {
int new_x = loc / len_n + direction[i];
int new_y = loc % len_n + direction[i + 1];
if (new_x >= 0 && new_x < len_m && new_y >= 0 && new_y < len_n &&
!visited[new_x][new_y] && edges[new_x][new_y] > 0) {
if (new_x * len_n + new_y == end) {
return dist + 1;
}
prio_que.emplace(dist + 1, new_x * len_n + new_y);
visited[new_x][new_y] = true;
}
}
}
return -1;
}
};
class Solution {
public:
int len_m;
int len_n;
vector> edges;
const int direction[5] = { 1, 0, -1, 0, 1 };
int cutOffTree(vector>& forest) {
edges = forest;
len_m = edges.size();
len_n = edges[0].size();
int ret = 0;
vector> pos_vec;
for (int i = 0; i < len_m; ++i) {
for (int j = 0; j < len_n; ++j) {
if (edges[i][j] > 1)
pos_vec.emplace_back(edges[i][j], i * len_n + j);
}
}
sort(pos_vec.begin(), pos_vec.end());
int len = pos_vec.size();
int pre = 0;
for (int i = 0; i < len; ++i) {
int temp = bfs(pre, pos_vec[i].second);
if (temp == -1)
return -1;
ret += temp;
pre = pos_vec[i].second;
}
return ret;
}
int bfs(int start, int end) {
if (start == end)
return 0;
int step = 1;
priority_queue, vector>, greater>> prio_que;
vector> costed(len_m, vector(len_n, INT_MAX));
costed[start / len_n][start % len_n] = abs(start / len_n - end / len_n) + abs(start % len_n - end % len_n);
prio_que.emplace(costed[start / len_n][start % len_n], 0, start);
while (!prio_que.empty()) {
auto front = prio_que.top();
prio_que.pop();
int cost = get<0>(front);
int dist = get<1>(front);
int loc = get<2>(front);
for (int i = 0; i < 4; ++i) {
int new_x = loc / len_n + direction[i];
int new_y = loc % len_n + direction[i + 1];
if (new_x >= 0 && new_x < len_m && new_y >= 0 && new_y < len_n &&
edges[new_x][new_y] > 0) {
if (new_x * len_n + new_y == end) {
return dist + 1;
}
int ncost = dist + 1 + abs(new_x - end / len_n) + abs(new_y - end % len_n);
if (ncost < costed[new_x][new_y]) {
prio_que.emplace(ncost, dist + 1, new_x * len_n + new_y);
costed[new_x][new_y] = ncost;
}
}
}
}
return -1;
}
};
