审题本题需要我们找出能使部队伤害值最小的路径中的最大伤害值思路题目要求我们需要将第n行的m个房间的机关都打开就是说我们的部队需要进入到每一个房间而我们是可以上下左右自由移动的所以只要能进入第n行的任意一个房间即可方法一二分答案多源bfs由于题目中需要找的是部队整体伤害值最小的路径中最大伤害值符合“最小值最大”模板我们尝试使用二分答案。二段性分析假设我们有一个满足题目要求的答案ret那么比ret伤害值大的路径一定存在而比ret伤害值小的路径一定不存在。这就是该题的答案具有的二段性我们只要在二分答案的时候用bfs搜索判断是否存在伤害值小于mid的最小路径若存在就说明答案区间在左侧让右指针更新为mid否则就更新左指针为mid1。最后得到的l或r的值就是答案解题#includeiostream #includequeue #includecstring using namespace std; const int N 1010; typedef pairint, int PII; int n, m; int p[N][N]; bool f[N][N]; int dx[] { 1,-1,0,0 }; int dy[] { 0,0,1,-1 }; bool bfs(int mid)//查找是否有伤害值小于mid的可行路径 { queuePII q; if (n 1) return true; //清空残留痕迹 memset(f, 0, sizeof(f)); //将多源点放入队列 for (int i 1; i m; i) { q.push({ 1,i }); f[1][i] true; } while (q.size()) { PII t q.front(); q.pop(); int x0 t.first, y0 t.second; for (int j 0; j 4; j) { int x x0 dx[j], y y0 dy[j]; if (x 1 x n y 1 y m f[x][y] false p[x][y] mid) { f[x][y] true; q.push({ x,y }); if (n x) { return true; } } } } return false; } int main() { //数据录入 cin n m; int l 0, r 0; for (int i 1; i n; i) { for (int j 1; j m; j) { cin p[i][j]; r max(p[i][j], r); } } //二分答案 while (l r) { int mid (l r) / 2; if (bfs(mid)) r mid; else l mid 1; } cout l endl; return 0; }疑问为什么二分答案最终得到的结果一定在原数组中存在因为二分查找可以将区间范围内所有的数涵盖到而答案一定存在于二分区间中所以经过bfs判断的结果一定是存在的注意1.痕迹清理由于本题要进行多次bfs操作所以我们需要对全局判断变量f数组进行数据清理而队列q则是每次bfs时进行创建即可f数组的作用是确保每条可能路径只走一次不重复走也就是每个节点最多走一次2.只有满足对应位置的索引合法且没有遍历过且对应值小于mid的才会插入插入时也要将遍历状况更新3.在bfs中我们让对应数值等于mid的情况也算作合法路径这是因为不算上这种情况在特殊情况下会导致解错误。P1902 刺杀大使 - 洛谷
算法题（174）：刺杀大使
审题本题需要我们找出能使部队伤害值最小的路径中的最大伤害值思路题目要求我们需要将第n行的m个房间的机关都打开就是说我们的部队需要进入到每一个房间而我们是可以上下左右自由移动的所以只要能进入第n行的任意一个房间即可方法一二分答案多源bfs由于题目中需要找的是部队整体伤害值最小的路径中最大伤害值符合“最小值最大”模板我们尝试使用二分答案。二段性分析假设我们有一个满足题目要求的答案ret那么比ret伤害值大的路径一定存在而比ret伤害值小的路径一定不存在。这就是该题的答案具有的二段性我们只要在二分答案的时候用bfs搜索判断是否存在伤害值小于mid的最小路径若存在就说明答案区间在左侧让右指针更新为mid否则就更新左指针为mid1。最后得到的l或r的值就是答案解题#includeiostream #includequeue #includecstring using namespace std; const int N 1010; typedef pairint, int PII; int n, m; int p[N][N]; bool f[N][N]; int dx[] { 1,-1,0,0 }; int dy[] { 0,0,1,-1 }; bool bfs(int mid)//查找是否有伤害值小于mid的可行路径 { queuePII q; if (n 1) return true; //清空残留痕迹 memset(f, 0, sizeof(f)); //将多源点放入队列 for (int i 1; i m; i) { q.push({ 1,i }); f[1][i] true; } while (q.size()) { PII t q.front(); q.pop(); int x0 t.first, y0 t.second; for (int j 0; j 4; j) { int x x0 dx[j], y y0 dy[j]; if (x 1 x n y 1 y m f[x][y] false p[x][y] mid) { f[x][y] true; q.push({ x,y }); if (n x) { return true; } } } } return false; } int main() { //数据录入 cin n m; int l 0, r 0; for (int i 1; i n; i) { for (int j 1; j m; j) { cin p[i][j]; r max(p[i][j], r); } } //二分答案 while (l r) { int mid (l r) / 2; if (bfs(mid)) r mid; else l mid 1; } cout l endl; return 0; }疑问为什么二分答案最终得到的结果一定在原数组中存在因为二分查找可以将区间范围内所有的数涵盖到而答案一定存在于二分区间中所以经过bfs判断的结果一定是存在的注意1.痕迹清理由于本题要进行多次bfs操作所以我们需要对全局判断变量f数组进行数据清理而队列q则是每次bfs时进行创建即可f数组的作用是确保每条可能路径只走一次不重复走也就是每个节点最多走一次2.只有满足对应位置的索引合法且没有遍历过且对应值小于mid的才会插入插入时也要将遍历状况更新3.在bfs中我们让对应数值等于mid的情况也算作合法路径这是因为不算上这种情况在特殊情况下会导致解错误。P1902 刺杀大使 - 洛谷
