`
huyifan951124
  • 浏览: 82729 次
社区版块
存档分类
最新评论

nyoj306 dfs+二分搜索

阅读更多

题目大意:中文题。

算法思路:这种思路确实对我来说很新颖,我也是看了解题报告才知道。说白了,二分最小值和最大值的差,如果这个差值能够从起点走到终点,则说明这个差值是可行的,那我们就在减小,二分左半部分,否则二分右半部分。

 
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define MAXN 105
#define INF 0x3f3f3f3f
int n;
int a[MAXN][MAXN],dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int MIN,MAX;
bool visited[MAXN][MAXN],ok;
void dfs(int x,int y,int left,int right)
{
    if(x==n&&y==n)
    {
        ok=true;
        return;
    }
    for(int i=0;i<4;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(!visited[nx][ny]&&1<=nx&&nx<=n&&1<=ny&&ny<=n&&left<=a[nx][ny]&&a[nx][ny]<=right)
        {
            visited[nx][ny]=true;
            dfs(nx,ny,left,right);
        }
    }
    return;
}
bool isOk(int k)
{
    for(int i=MIN;i<=MAX;i++)
    {

        if(i+k>MAX)
            break;
        if(a[1][1]<i||a[1][1]>i+k)
            continue;
        if(a[n][n]<i||a[n][n]>i+k)
            continue;
        memset(visited,false,sizeof(visited));
        ok=false;
        visited[1][1]=true;
        dfs(1,1,i,i+k);
        if(ok)
            return true;
    }
    return false;

}
int main()
{


    while(~scanf("%d",&n))
    {

        MIN=INF;MAX=-INF;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                scanf("%d",&a[i][j]);
                if(MIN>a[i][j])
                    MIN=a[i][j];
                if(MAX<a[i][j])
                    MAX=a[i][j];
            }
        }
        int l=0,r=MAX-MIN;
        while(l<r)
        {
            int mid=(l+r)/2;
            if(isOk(mid))
                r=mid;
            else
                l=mid+1;
        }
        printf("%d\n",r);
    }


    return 0;
}


        

 

0
0
分享到:
评论

相关推荐

    nyoj部分ACM答案

    此代码采用了深度优先搜索(DFS)策略来完成任务。 #### 代码详解 ##### 引入头文件 ```cpp #include #include ``` 这里引入了两个常用的头文件:`iostream`用于处理标准输入输出流,而`stdio.h`则是C语言的标准...

    ACM在线评测系统 NYOJ 题库 离线看题网页版 nyoj

    NYOJ,全称为南阳理工学院在线评测系统(Nanyang Institute of Technology Online Judge),是为ACM(国际大学生程序设计竞赛)以及其他编程爱好者提供的一种在线编程练习平台。该系统支持用户提交代码并进行实时...

    NYOJ题目 离线版

    NYOJ(New York Online Judge)是一个在线编程竞赛平台,主要面向ACM(国际大学生程序设计竞赛)的参与者。这个离线版包含了NYOJ的所有题目,为编程爱好者和参赛者提供了一个方便的本地化练习环境。通过爬虫技术,...

    ACM题库题库啊

    通过练习这些题目,参赛者可以熟练掌握排序、搜索、图论、动态规划等经典算法,同时提升对问题的抽象和建模能力。此外,ACM题目的解决过程也强调了代码的可读性和调试技巧,这对任何程序员来说都是宝贵的技能。 ...

    nyoj16.rar_site:www.pudn.com

    标题中的“nyoj16.rar”可能是指一个编程竞赛或者在线判题系统(如NOIP、NYOJ)的问题编号16的题目,而“site:www.pudn.com”通常用于搜索引擎查询,表明这个压缩文件可能来源于PUDN(普渡大学电子论坛)这个网站。...

    算法-矩形嵌套(NYOJ-16)(包含源程序).rar

    《算法-矩形嵌套(NYOJ-16)》是针对计算机科学中的一个典型问题进行探讨的资源包,其中包含了解决该问题的源程序。这个问题涉及到数据结构、图论以及算法设计等多个核心领域,是编程竞赛或算法学习中的常见题目。在...

    nyoj 61 传纸条(一)

    双线程动态规划问题,很值得练习。传一个ac代码,测试一下csdn的功能。

    NYOJ.290.DictionaryTree.zip_trie树c_字典树_高级数据结构

    在NYOJ.290.DictionaryTree.cpp文件中,可能包含了以下内容: 1. `TrieNode`结构体定义,用于表示Trie树的节点。 2. 插入函数,如`insert(char *str)`,用于将字符串插入到Trie树中。 3. 查询函数,如`search(char *...

    nyoj_lvy实战开发系列《二》: 微信端开发:登录小程序

    这个小程序的主要目的是为了用户用微信的用户信息登录后将用户信息授权存入自己的数据库中,这样以后每次微信登录得到的code 所得到的 openid 可以在项目的数据库中查到该用户的相关信息。 在测试的过程中,需要用户...

    nyoj_lvy实战开发系列《三》: 获取城市信息

    由于微信小程序没有方法可以获得当前用户所在城市的信息,所以需要调用方法来获取城市信息,用了两个方法去发送请求并返回城市信息  1. @Controller public class WechatLocationManager { private Logger logger ...

    nyoj_lvy实战开发系列《一》:发送JSON信息,加密数据解密算法,UnionID机制说明

    前期小程序开发只进行到根据微信用户登录获取的code 去微信的API去获取到该用户的openId和session_key,到了第二阶段,老大让我重写OAuthManager的代码来实现微信小程序和微信公众号平台获取用户信息的优化,即将...

    南阳理工oj stl练习ac代码

    南阳理工的OJ平台可能包含ACM风格的题目,比如动态规划、图论、搜索等问题,通过AC代码,我们可以学习如何在有限的时间内构造高效解决方案。 6. NYOJ系统: NYOJ(南阳理工在线判题系统)是南阳理工学院开发的OJ...

    南阳理工学院OJ第1版解题报告V1.0.pdf

    深度优先搜索(DFS)的应用实例,用于探索图或网格中的所有可能路径。 #### 21. 三个水杯 广度优先搜索(BFS)的示例,适用于状态空间较小且需要探索所有可能性的情况。 #### 22. 素数求和问题 素数筛法(如...

    经典动态规划 南阳104最大和

    给定一个由整数组成二维矩阵(r*c),现在需要找出它的一个子矩阵,使得这个子矩阵内的所有元素之和最大,并把这个子矩阵称为最大子矩阵。

Global site tag (gtag.js) - Google Analytics