|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 广东范戴克 于 2024-10-8 16:24 编辑
题目是洛谷的p1902刺杀大使
这个账号没权限发链接
只能过两个测试点,其他的都是TLE,有没有彦祖看一下错在哪
某组织正在策划一起对某大使的刺杀行动。他们来到了使馆,准备完成此次刺杀,要进入使馆首先必须通过使馆前的防御迷阵。
迷阵由 n×m 个相同的小房间组成,每个房间与相邻四个房间之间有门可通行。在第 n 行的 m 个房间里有 m个机关,这些机关必须全部打开才可以进入大使馆。而第 1 行的 m 个房间有 m 扇向外打开的门,是迷阵的入口。除了第 1 行和第 n 行的房间外,每个房间都被使馆的安保人员安装了激光杀伤装置,将会对进入房间的人造成一定的伤害。第 i 行第 j 列 造成的伤害值为 pi,j (第 1 行和第 n 行的 p 值全部为 0)。
现在某组织打算以最小伤害代价进入迷阵,打开全部机关,显然,他们可以选 择任意多的人从任意的门进入,但必须到达第 n 行的每个房间。一个士兵受到的伤害值为他到达某个机关的路径上所有房间的伤害值中的最大值,整个部队受到的伤害值为所有士兵的伤害值中的最大值。现在,这个恐怖组织掌握了迷阵的情况,他们需要提前知道怎么安排士兵的行进路线可以使得整个部队的伤害值最小。
输入格式
第一行有两个整数 n,m,表示迷阵的大小。
接下来 n 行,每行 m 个数,第 i 行第 j 列的数表示 pi,j。
输出格式
输出一个数,表示最小伤害代价。
说明/提示
50% 的数据,n,m≤100;
100%的数据,n,m≤1000;
pi,j≤1000
- #include<iostream>
- #include<cstring>
- #include<math.h>
- #include<algorithm>
- using namespace std;
- int d[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
- int ans = 1000;
- int n, m, temp, my_max = 0, my_min = 1000;
- short book[1003][1003];
- short p[1003][1003];
- bool flag = false,r;
- int main() {
- bool check(int x, int y, int num);
- cin >> n >> m;
- for (int i = 1; i <= n; i++)
- for (int j = 1; j <= m; j++) {
- cin >> temp;
- p[i][j] = temp;
- if (temp > my_max)
- my_max = temp;
- if (temp < my_min)
- my_min = temp;
- }
- int mid;
- while (my_min <= my_max) {
- mid = (my_min + my_max) / 2;
- flag = false;
- memset(book, 0, sizeof(book));
- if (check(1, 1, mid)) {
- ans = mid;
- my_max = mid-1;
- }
- else
- my_min = mid+1;
- }
- cout << ans;
- }
- bool check(int x,int y,int num)
- {
- int tx, ty;
- if (x == n||flag) {
- flag = true;
- r = true;
- return r;
- }
- for (int i = 0; i < 4; i++) {
- tx = x + d[i][0];
- ty = y + d[i][1];
- if (book[tx][ty] == 1 || p[tx][ty] > num||tx>n||ty>m||tx<1||ty<1)
- continue;
- book[tx][ty] = 1;
- check(tx, ty, num);
- book[tx][ty] = 0;
- if (flag)
- return flag;
- }
- return flag;
- }
复制代码
对于洛谷的这道题目,你需要在一个网格中寻找路径,这个路径要穿越从左上到右下,但代价最小。为了优化你的代码,从而让它通过更大规模的测试点,需要一些技巧。
基于你提供的信息和常见的路径优化问题,建议你优化算法如下:
1. **二分+判断可行性**:
- 使用二分搜索来尝试所有可能的最大高度差。
- 每次二分后,通过广度优先搜索(BFS)或深度优先搜索(DFS)来判断当前高度差是否可行。
2. **广度优先搜索(BFS)**:
- 使用BFS更合适在这种最短路径相关的问题中,因为它可以在早期阶段就找到可行路径并及时跳出。
具体步骤如下:
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <algorithm>
- using namespace std;
- int n, m;
- vector<vector<int>> grid;
- vector<vector<bool>> visited;
- bool canReachWithMaxDiff(int maxDiff) {
- visited.assign(n, vector<bool>(m, false));
- queue<pair<int, int>> q;
- q.push({0, 0});
- visited[0][0] = true;
-
- vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
-
- while (!q.empty()) {
- auto [x, y] = q.front();
- q.pop();
-
- if (x == n - 1 && y == m - 1) {
- return true;
- }
-
- for (auto [dx, dy] : directions) {
- int nx = x + dx, ny = y + dy;
- if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny] &&
- abs(grid[nx][ny] - grid[x][y]) <= maxDiff) {
- visited[nx][ny] = true;
- q.push({nx, ny});
- }
- }
- }
- return false;
- }
- int main() {
- cin >> n >> m;
- grid.resize(n, vector<int>(m));
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- cin >> grid[i][j];
- }
- }
-
- int left = 0, right = 1000, ans = 1000;
- while (left <= right) {
- int mid = left + (right - left) / 2;
- if (canReachWithMaxDiff(mid)) {
- ans = mid;
- right = mid - 1;
- } else {
- left = mid + 1;
- }
- }
- cout << ans << endl;
- return 0;
- }
复制代码
### 解释:
- **二分搜索**:我们以高度差作为指标进行二分,寻找瓶颈的最小值。
- **BFS 判断可行性**:对每个中间值,通过 BFS 检查从起点到终点是否有连通路径,且路径中相邻点的差值不超过该中间值。
- **复杂度**:这结合了二分搜索和 BFS 的复杂度,总体可以处理较大的输入规模。
通过这种方法,大部分在 `n, m ≤ 1000` 时都可以正常运行在时间限制内。记得理解算法的基本思路,针对具体问题需求可以进一步调整。
以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
|
|