今天来讲一下P1902 刺杀大使，也是一道二分题。通过昨天的题目二分模板已经没有什么问题了。先贴一下代码。

#include <bits/stdc++.h>
using namespace std;

bool check(const vector<vector<int>>& p, int n, int m, int mid) {
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    queue<pair<int, int>> q;
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    q.push({0, 0});
    visited[0][0] = true;
    while (!q.empty()) {
        auto curr = q.front();
        q.pop();
        
        for (const auto& dir : dirs) {
            int ni = curr.first + dir[0];
            int nj = curr.second + dir[1];
            
            if (ni >= 0 && ni < n && nj >= 0 && nj < m && !visited[ni][nj] && p[ni][nj] <= mid) {
                if (ni == n-1) {  // 只要到达第n-1行的任意一个点就可以返回
                    return true;
                }
                visited[ni][nj] = true;
                q.push({ni, nj});
            }
        }
    }
    
    return false;
}
int main (){
    int n, m;
    cin >> n >> m;
    vector<vector<int>> p(n, vector<int>(m));
    
    int min_p = 1000;
    int max_p = 0;
    
    // 读取所有行数据
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> p[i][j];
            // 只考虑中间行（第1到n-2行）的伤害值
            if (i > 0 && i < n-1) {
                min_p = min(min_p, p[i][j]);
                max_p = max(max_p, p[i][j]);
            }
        }
    } 
    int left = 0;
    int right = max_p;
    int answer = max_p;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (check(p, n, m, mid)) {
            answer = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << answer << endl;
    return 0;
    
}

这道题也就是判断的那个函数稍微复杂一点，因为要判断有没有一条路线所受到的伤害最小，而每个房间都可以向周围的四个房间移动。这样我就想到了广度遍历，每个房间向周围的四个房间遍历。实现了这个就能把题目做出来，当然采用DFS或者是并查集也是可以的。