欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

nyoj306 dfs+二分搜索

程序员文章站 2022-07-10 09:18:38
...

题目大意:中文题。

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

 
#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;
}


        

 

相关标签: 算法 dfs 二分