P1902 刺杀大使https://www.luogu.com.cn/problem/P1902二分BFS二分是对单调区间的快速枚举当出现关键词“最大”“最小”时使用。在二分的基础上就是Check验证答案是否合法。本题是一个矩阵涉及到对dfs和bfs的选择。DFS递归实现的函数栈调用最坏情况下为O(n×m)超过C默认栈空间会导致栈溢出。手写栈的情况另做验证。在此选择BFS作为check的实现方式。不需要记录路径只要存在路径即可返回会相应地降低时间复杂度。手写队列进行深度搜索。完整代码如下#includebits/stdc.h#definenxxdx[i]#definenyydy[i]usingnamespacestd;intn,m;ints[1005][1005],dx[4]{0,0,1,-1},dy[4]{1,-1,0,0};inlineintread(){intx0,f1;charchgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9)xx*10ch-0,chgetchar();returnx*f;}boolvis[1005][1005];boolbfs(intmaxn){queuepairint,intq;q.push({1,1}),vis[1][1]1;while(!q.empty()){intxq.front().first,yq.front().second;if(xn)return1;q.pop();for(inti0;i4;i){if(nx1||nxn||ny1||nym||s[nx][ny]maxn||vis[nx][ny])continue;vis[nx][ny]1;q.push({nx,ny});}}return0;}intmain(){cinnm;for(inti1;in;i)for(intj1;jm;j)s[i][j]read();intl0,r1000,ansr;while(lr){intmid(lr)/2;memset(vis,0,sizeof(vis));if(bfs(mid))ansmid,rmid-1;elselmid1;}coutans;return0;}
P1902 刺杀大使https://www.luogu.com.cn/problem/P1902二分BFS二分是对单调区间的快速枚举当出现关键词“最大”“最小”时使用。在二分的基础上就是Check验证答案是否合法。本题是一个矩阵涉及到对dfs和bfs的选择。DFS递归实现的函数栈调用最坏情况下为O(n×m)超过C默认栈空间会导致栈溢出。手写栈的情况另做验证。在此选择BFS作为check的实现方式。不需要记录路径只要存在路径即可返回会相应地降低时间复杂度。手写队列进行深度搜索。完整代码如下#includebits/stdc.h#definenxxdx[i]#definenyydy[i]usingnamespacestd;intn,m;ints[1005][1005],dx[4]{0,0,1,-1},dy[4]{1,-1,0,0};inlineintread(){intx0,f1;charchgetchar();while(ch0||ch9){if(ch-)f-1;chgetchar();}while(ch0ch9)xx*10ch-0,chgetchar();returnx*f;}boolvis[1005][1005];boolbfs(intmaxn){queuepairint,intq;q.push({1,1}),vis[1][1]1;while(!q.empty()){intxq.front().first,yq.front().second;if(xn)return1;q.pop();for(inti0;i4;i){if(nx1||nxn||ny1||nym||s[nx][ny]maxn||vis[nx][ny])continue;vis[nx][ny]1;q.push({nx,ny});}}return0;}intmain(){cinnm;for(inti1;in;i)for(intj1;jm;j)s[i][j]read();intl0,r1000,ansr;while(lr){intmid(lr)/2;memset(vis,0,sizeof(vis));if(bfs(mid))ansmid,rmid-1;elselmid1;}coutans;return0;}
