牛客周赛51:小红走矩阵(二分+bfs)

链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
 

题目描述

给定n×nn \times nn×n的矩阵,矩阵中的每个元素都是正整数,小红能当前位于左上角(1,1)(1,1)(1,1),每次可以从 (x,y)(x, y)(x,y) 走到 (x+1,y)(x+1, y)(x+1,y)、(x,y+1)(x, y+1)(x,y+1)、(x−1,y)(x-1, y)(x−1,y)、(x,y−1)(x, y-1)(x,y−1),但不能走出矩阵。小红希望找到一条到右下角(n,n)(n,n)(n,n)的路径,定义路径权值为路径上经过的每个点的最大值,求所有路径中的最小路径权值。

输入描述:

第一行一个整数nnn,表示矩阵的大小。
接下来nnn行,每行nnn个整数,表示矩阵中的元素aija_{ij}aij​。
1≤n≤5001 \leq n \leq 5001≤n≤500
1≤aij≤1091 \leq a_{ij} \leq 10^91≤aij​≤109。

输出描述:

输出一个整数,表示所有路径中的最小路径权值。

示例1

输入

复制3 3 2 1 6 5 4 9 8 7

3
3 2 1
6 5 4
9 8 7

输出

复制7

7

说明

先一直往右走,再一直往下走,路径上的最大值为7。

做法

二分。当时想到了要用二分,但又没往那方面深想。。。没想到怎么bfs,想直接用bfs写的。最后去搞dp做法,也没弄出来,好像不能dp?

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[510][510];
int vis[510][510];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
struct ty{
    int x,y;
};
queue<ty> q;
int isleft(long long x){
    memset(vis,0,sizeof(vis));
    q=queue<ty> ();
    if(a[1][1]>x) return 1;
    vis[1][1]=1;
    q.push({1,1});
    while(!q.empty()){
        ty tmp=q.front();
        q.pop();
        for(int i=0;i<4;i++){
            int xx=tmp.x+dx[i];
            int yy=tmp.y+dy[i];
            if(vis[xx][yy]) continue;
            if(xx>n||yy>n||xx<1||yy<1) continue;
            if(a[xx][yy]>x) continue;
            if(xx==n&&yy==n) return 0;
            q.push({xx,yy});
            vis[xx][yy]=1;
        }
    }
    return 1;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%lld",&a[i][j]);
        }
    }
    long long l=0,r=1e9+1;
    while(l+1<r){
        long long mid=l+(r-l)/2;
        if(isleft(mid)) l=mid;
        else r=mid;
    }
    cout<<r;
}

相关推荐

  1. 51矩阵二分+bfs

    2024-07-20 20:32:04       31 阅读
  2. 51

    2024-07-20 20:32:04       31 阅读
  3. Round 51

    2024-07-20 20:32:04       27 阅读
  4. Round 51题解

    2024-07-20 20:32:04       25 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-20 20:32:04       141 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-20 20:32:04       156 阅读
  3. 在Django里面运行非项目文件

    2024-07-20 20:32:04       129 阅读
  4. Python语言-面向对象

    2024-07-20 20:32:04       141 阅读

热门阅读

  1. 设计模式--外观模式

    2024-07-20 20:32:04       27 阅读
  2. Kylin Cube Designer:数据洞察的魔法画布

    2024-07-20 20:32:04       22 阅读
  3. opencv读写路径包含中文的文件

    2024-07-20 20:32:04       28 阅读
  4. 探索Web世界:WebKit的地理位置API

    2024-07-20 20:32:04       32 阅读
  5. OpenCV从基础到入门(基于python)

    2024-07-20 20:32:04       24 阅读
  6. 运维 | Linux 系统中 MySQL 的安装与使用记录

    2024-07-20 20:32:04       25 阅读
  7. GPT-4o 与 GPT-4o Mini:两者的区别和特点

    2024-07-20 20:32:04       30 阅读
  8. GO Channel使用详解(各种场景下的最佳实践)

    2024-07-20 20:32:04       25 阅读