[已解决]洛谷刺杀大使20分求改

广东范戴克

题目是洛谷的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;
}

最佳答案

月排行榜 / 总排行榜

FishC

2024-10-8 16:23:55

广东范戴克 发表于 2024-10-08 16:23
输入格式
第一行有两个整数 n,m，表示迷阵的大 ...

对于洛谷的这道题目，你需要在一个网格中寻找路径，这个路径要穿越从左上到右下，但代价最小。为了优化你的代码，从而让它通过更大规模的测试点，需要一些技巧。

基于你提供的信息和常见的路径优化问题，建议你优化算法如下：

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 小助理，如未能正确解答您的问题，请继续追问。

跳转到最佳答案楼层

FishC

你遇到了超时问题（TLE），通常是因为算法复杂度过高或有不必要的重复计算。根据你提供的代码片段，无法完整评估整个算法，不过我可以给出一些建议来优化代码。

1. **使用更高效的数据结构**：
   你可以考虑使用二维数组或向量来存储输入数据及常用的状态信息，以便于快速访问和更新。

2. **减少不必要的计算**：
   - 确保在搜索时（例如深度优先搜索 DFS）系统地检查每一步是否是必要的。
   - 预处理数据以避免重复计算，例如记录访问过的状态避免重复访问。

3. **利用更快的I/O操作**：
   - 如果输入规模较大，使用`scanf`和`printf`可能比`cin`和`cout`更快。

4. **优化你的算法思路**：
   - 考虑其他方法，如动态规划、二分查找等优化搜索算法。

这里有一个可能的算法结构建议：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 用于表示一个位置
struct Point {
    int x, y;
};

int n, m;
vector<vector<int>> grid;
vector<vector<bool>> visited;

// 四个方向移动
vector<Point> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

// 验证是否在界内
inline bool isInBounds(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

// 递归搜索
void dfs(int x, int y, int& ans) {
    for (const auto& dir : directions) {
        int nx = x + dir.x, ny = y + dir.y;
        if (isInBounds(nx, ny) && !visited[nx][ny]) {
            visited[nx][ny] = true;
            // 可以在这里判断是否是更优的路径或更新ans
            dfs(nx, ny, ans);
            visited[nx][ny] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    grid.assign(n, vector<int>(m));
    visited.assign(n, vector<bool>(m, false));
    int my_max = 0, my_min = 1000;

    // 获取输入和初始化界限
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
            my_max = max(my_max, grid[i][j]);
            my_min = min(my_min, grid[i][j]);
        }
    }

    // 主逻辑
    int ans = 1000;  // 假设这是目标结果的初始值
    // 调用dfs等函数，结合判断条件逐步逼近答案

    cout << ans << endl;
    return 0;
}

请根据你的实际情况调整细节。这些只是常见的优化思路，具体的效率取决于对问题的深刻理解和针对性优化。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

广东范戴克

输入格式
第一行有两个整数 n,m，表示迷阵的大小。
接下来 n 行，每行 m 个数，第 i 行第 j 列的数表示 pi,j。
输出格式
输出一个数，表示最小伤害代价。
说明/提示
50% 的数据，n,m≤100;
100%的数据，n,m≤1000;
pi,j≤1000

FishC

广东范戴克 发表于 2024-10-08 16:23
输入格式
第一行有两个整数 n,m，表示迷阵的大 ...

对于洛谷的这道题目，你需要在一个网格中寻找路径，这个路径要穿越从左上到右下，但代价最小。为了优化你的代码，从而让它通过更大规模的测试点，需要一些技巧。

基于你提供的信息和常见的路径优化问题，建议你优化算法如下：

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 小助理，如未能正确解答您的问题，请继续追问。

广东范戴克

#include<iostream>
#include<math.h>
#include<algorithm>
#include<queue>
typedef pair<int, int>point;

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(short)*1003*1003);
                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;
        queue<point>q;
        point a(1, 1);
        q.push(a);
        book[1][1] = 1;
        while (!q.empty()) {
                point top = q.front();
                for (int i = 0; i < 4; i++) {
                        point next;
                        tx = top.first + d[i][0];
                        ty = top.second + 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;
                        next.first = tx;
                        next.second = ty;
                        q.push(next);
                        if (tx == n)
                                return true;
                }
                q.pop();
        }
        return false;
}
以上代码为什么编译失败呀

FishC

广东范戴克 发表于 2024-10-09 17:04
#include
#include
#include
#include
typedef pa ...

你的代码在编译时出现了几个问题，我们把它们一一解决：

1. **缺少头文件和语法错误：**
   - `#include`后缺少头文件名称。例如：`#include <iostream>`等。
   - `typedef pairpoint;`是错误的，应该是`typedef pair<int, int> point;`

2. **数组定义和类型错误：**
   - `int d = {{0,1},{1,0},{0,-1},{-1,0}};`应该是`int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};`

3. **变量定义错误：**
   - `short book;`和`short p;`并未正确初始化为数组。应该定义为二维数组，比如`short book[1005][1005];` 和 `short p[1005][1005];`

4. **`main`函数中的函数定义问题：**
   - `bool check(int x, int y, int num);`应在`main`函数外部，并定义为一个完整的函数。

5. **读取数据时的错误：**
   - 缺乏读取方式。应该用`cin >> p[i][j];`类似地进行读取。

结合这些修改，下面是一个简化和修正后的版本框架：

#include <iostream>
#include <queue>
#include <utility>

using namespace std;
typedef pair<int, int> point;

int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};
int n, m, my_max = 0, my_min = 1000;
short book[1005][1005] = {0};
short p[1005][1005];

bool check(int x, int y, int num);

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> p[i][j];
            if (p[i][j] > my_max) my_max = p[i][j];
            if (p[i][j] < my_min) my_min = p[i][j];
        }
    }

    // 示例逻辑，可以根据实际需求调整和完善
    int mid;
    while (my_min < my_max) {
        mid = (my_min + my_max) / 2;
        if (check(1, 1, mid)) {
            my_max = mid;
        } else {
            my_min = mid + 1;
        }
    }
    cout << my_min << endl;
    return 0;
}

bool check(int x, int y, int num) {
    queue<point> q;
    q.push({x, y});
    book[x][y] = 1;

    while (!q.empty()) {
        point cur = q.front();
        for (int i = 0; i < 4; ++i) {
            int tx = cur.first + d[i][0];
            int ty = cur.second + d[i][1];

            if (tx < 1 || ty < 1 || tx > n || ty > m || book[tx][ty] || p[tx][ty] > num) continue;

            book[tx][ty] = 1;
            q.push({tx, ty});
            if (tx == n) return true;
        }
        q.pop();
    }
    return false;
}

以上代码为你提供了一个更正后的结构框架，可以通过这个框架进行进一步调试和完善。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。