多源BFS：刺杀大使

题目P1902 刺杀大使 - 洛谷先看题目数据范围不是很大。这道题求最大值最小化我们应该想到用二分。把第一行的每个数加入队列多源BFS找出伤害值不超过mid的情况能否一条到达第n行的路线只要有一条通道能成功能通向终点那就返回true#include iostream #include algorithm #include queue #include cstring using namespace std; const int N 1010; int n, m; int a[N][N]; bool st[N][N]; int r 0; int l 0; int dx[] {0, 1, 0, -1}; int dy[] {1, 0, -1, 0}; typedef pairint, int PII; bool bfs(int mid) { queuePII q; memset(st, 0, sizeof(st)); if (n 1) return true; for (int i 1; i m; i) { q.push({1, i}); } while(q.size()) { auto t q.front(); q.pop(); int x1 t.first, y1 t.second; for (int i 0; i 4; i) { int x2 x1dx[i], y2 y1 dy[i]; if (x2 1 || x2 n || y2 1 || y2 m || a[x2][y2] mid || st[x2][y2]) continue; st[x2][y2] true; if (x2 n) return true; q.push({x2, y2}); } } return false; } int main() { cin n m; for (int i 1; i n; i) { for (int j 1; j m; j) { cin a[i][j]; r max(r, a[i][j]); } } while(l r) { int mid (lr)/2; if (bfs(mid)) r mid; //最大值最小化 else l mid1; } cout l endl; return 0; }