华为0507机试

题目二 建设基站

有一棵二叉树，每个节点上都住了一户居民。现在要给这棵树上的居民建设基站，每个基站只能覆盖她所在与相邻的节点，请问信号覆盖这棵树最少需要建设多少个基站

#include <bits/stdc++.h>
using namespace std;const int N = 3010;struct Node {int val;Node*left, *right;Node (int _val) : left(nullptr), right(nullptr){val = _val;}
};int num[N];
Node* root;
int tot = 0;
const int INF = 1e8;void build() {root = new Node(num[0]);queue<Node*> q;q.push(root);int i = 1;while (!q.empty()) {if (i == tot) break;auto node = q.front();q.pop();if (num[i] != -1) {auto l = new Node(num[i]);node->left = l;q.push(l);} else {node->left = nullptr;}i++;if (num[i] != -1) {auto r = new Node(num[i]);node->right = r;q.push(r);} else {node->right = nullptr;}i++;}
}vector<int> dfs(Node* root) {if (!root) return {0, 0, INF};auto l = dfs(root->left), r = dfs(root->right);return {min(l[1], l[2]) + min(r[1], r[2]),min(l[2] + min(r[1], r[2]), r[2] + min(l[1], l[2])),min(l[0], min(l[1], l[2])) + min(r[0], min(r[1], r[2])) + 1};
}int main() {string line;getline(cin, line);stringstream ssin(line);string n;int i = 0;while (ssin >> n) {tot++;if (n != "N") {num[i] = stoi(n);} else {num[i] = -1;}i++;}build();auto f = dfs(root);cout << min(f[1], f[2]) << endl;return 0;
}

题目三 最小代价相遇的路径规划

假定有两辆车在给定一个 n x n 的非负整数矩阵地图 grid中行驶，地图左上角位置为[0, 0]。我们简化车辆行驶的方式，每辆车可以从一个坐标行驶到相邻（上下左右）的另一个坐标，并且经过的每个位置都会产生代价，包括起始位置的代价。其中 grid[i] [j] 表示通过网格位置 [i, j] 所需的代价。矩阵中，grid[i] [j] 等于 0 表示该位置为障碍物，车辆无法通过。
两辆车约定好需要在地图中快速相遇进行货物交接。两辆车相遇的定义为：两辆车最终分别停在相邻的网格位置（上下或左右相邻），并且路径可达。 两辆车相遇所需的代价定义为：两辆车到达各自相遇位置所需代价中的较大值。 注意：路径代价包含车辆的起始位置位置的代价；行驶过程中，车辆可以停在某一个网格位置上，两辆车无需同步行驶。
求两辆车可以相遇需要的最小代价，如果无法相遇则返回 -1 。

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int g[N][N];
int n;
int ca[N][N], cb[N][N];
int res = INT_MAX;
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int main() {cin >> n;for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)cin >> g[i][j];memset(ca, 0x3f, sizeof ca);memset(cb, 0x3f, sizeof cb);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (!g[i][j]) continue;if (!i && !j) ca[i][j] = g[i][j];else {if (i) ca[i][j] = min(ca[i][j], ca[i-1][j] + g[i][j]);if (j) ca[i][j] = min(ca[i][j], ca[i][j-1] + g[i][j]);}}}for (int i = n - 1; i >= 0; i--) {for (int j = n-1; j >= 0; j--) {if (!g[i][j]) continue;if (i == n-1 && j == n-1) cb[i][j] = g[i][j];else {if (i != n-1) cb[i][j] = min(cb[i][j], cb[i+1][j] + g[i][j]);if (j != n-1) cb[i][j] = min(cb[i][j], cb[i][j+1] + g[i][j]);}}}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {for (int t = 0; t < 4; t++) {int x = i + dx[t], y = j + dy[t];if (x < 0 || x >= n || y < 0 || y >= n) continue;res = min(res, max(ca[i][j], cb[x][y]));}}}if (res >= 0x3f) cout << -1 << endl;else cout << res << endl;return 0;
}