二分+Dfs【p1902】刺杀大使

题目描述--->p1902 刺杀大使

题意概括：

找一条路径,使得从第1行到第n行路径的最大值最小。

分析：

题目概括出来,很容易想到二分.

求最大值最小,因此我们可以对最大伤害值进行二分。

如果某位置所受伤害值大于我们当前所限制的伤害值,我们肯定是不走这条路的.

栗子：

我们限制最大伤害为5

搜索到某一行发现伤害值是这样的--> 8 8 8 8。

这样我们是无法通过这一行的。

做法：

我们需要标记是否能以当前限制的伤害值走到最后一行,如果可以我们就去寻求更小伤害,如果不能我们只能去寻求较小伤害(实际上是更大了)。

以标记作为更新边界的标准.

所以很容易写出二分代码↓

int l=0,r=1008;

//这里右边界赋为了极大值

//数据保证了每个位置伤害值不超过1000

//也可以把右边界赋值为当前图中最大伤害值.

	while(l<=r)//一般套路

	{

		int mid=l+r>>1;

		memset(vis,0,sizeof vis);

		flg=false;

		dfs(1,1,mid);

		if(flg==true)//flg为true视为能到达最后一行

			r=mid-1;//因此我们更新右边界,寻求更小值

		else l=mid+1;

	}

搜索部分代码如何去写？

没什么需要特别注意的地方。

需要判断:是否超出边界,是否遍历过,伤害值是否能满足限制条件.

我写出来是这个样子的↓

IL void dfs(int x,int y,int mid)

{

    if(x==n)

    {

        flg=1;

        return;

    }

    vis[x][y]=true;

    for(RI i=0,xx,yy;i<4;++i)

    {

        xx=x+ax[i],yy=y+ay[i];

        //ax,ay数组为搜索的一般设置套路.代表四个方向

        //const int ax[]={0,1,0,-1};

        //const int ay[]={1,0,-1,0};

        if(xx<1 or xx>n or yy<1 or yy>m or vis[xx][yy] or p[xx][yy]>mid)//一连串判断

        //这里的 or 与 || 是一样的

            continue;

        dfs(xx,yy,mid);

        if(flg)

            return;

    }

}

一点时间优化

我们可以不必将vis数组重置,而去判断是第几次经过.

--------------------代码---------------------

#include<bits/stdc++.h>

#define IL inline

#define RI register int

#define mod 100000

IL void read(int &x){

	int f=1;x=0;char s=getchar();

	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}

	while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,m,p[1008][1008],tm;

const int ax[]={0,1,0,-1};

const int ay[]={1,0,-1,0};

bool flg,vis[1008][1008];

IL void dfs(int x,int y,int mid)

{

    if(x==n)

    {

        flg=1;

        return;

    }

    vis[x][y]=true;

    for(RI i=0,xx,yy;i<4;++i)

    {

        xx=x+ax[i],yy=y+ay[i];

        if(xx<1 or xx>n or yy<1 or yy>m or vis[xx][yy] or p[xx][yy]>mid)

            continue;

        dfs(xx,yy,mid);

        if(flg)

            return;

    }

}

int main()

{

	read(n),read(m);

	for(RI i=1;i<=n;i++)

		for(RI j=1;j<=m;j++)

			read(p[i][j]);

	int l=0,r=1008;

	while(l<=r)

	{

		int mid=l+r>>1;

		memset(vis,0,sizeof vis);

		flg=false;

		dfs(1,1,mid);

		if(flg==true)

			r=mid-1;

		else l=mid+1;

	}

	printf("%d",l);

}

巴特西

二分+Dfs【p1902】刺杀大使

最新文章

热门文章