wxwoo's blog

原题目链接

看到题目就想到了dfs+剪枝

然后就想到了dfs有问题

例如这组数据

1
2
3
4-9-12
| | |
2-4-10

从4开始,到10结束

dfs会走$4 \to 2 \to 4 \to 10$,答案为8

然而很明显走$4 \to 9 \to 4 \to 10$更优,答案为6

当然你加一大堆玄学优化也是可以搜出正确答案的

这里不再多讲,而是提供另一种思路:

二分

$Q:$二分什么呢?

$A:$二分答案啊……这不是废话吗……

$Q:$我还不知道二分答案啊!关键是$check$函数怎么写!

$A:$这个时候我们就要祭出$dfs$大法了!

刚才还说dfs有问题现在就用

  • check函数循环最小值,最大值用最小值+答案计算出

  • 对整张表dfs,标记数值在最小值到最大值区间内的格子

  • 若目标点被标记,返回true,否则继续循环,直到循环结束,返回false

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,move[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int m[N][N],n,ans=0;
bool visit[N][N];
template<typename T>inline void read(T &x)//快读
{
char ch=getchar();
T f=1;
x=0;
while(!('0'<=ch&&ch<='9'))
{
if(ch=='-')
f=-1;
ch=getchar();
}
do
{
x=(x<<3)+(x<<1)+ch-48;
ch=getchar();
}while('0'<=ch&&ch<='9');
x*=f;
}
void dfs(int x,int y,const int& sml,const int& big)//sml即为最小值,big即为最大值
{//dfs板子,不作过多解释
if(visit[x][y])
return;
visit[x][y]=true;
for(int i=0;i<4;i++)
{
int nx=x+move[i][0],ny=y+move[i][1];
if(nx<1||nx>n||ny<1||ny>n)
continue;
if(m[nx][ny]<sml||m[nx][ny]>big)//若不在最小值到最大值区间内,则continue
continue;
dfs(nx,ny,sml,big);
}
}
inline bool check(int x)//x即为要检验的答案
{
for(int i=max(0,max(m[1][1],m[n][n])-x);i<=min(110-x,min(m[1][1],m[n][n]));i++)
//最小值的初值:从起点和终点里取最大的(不然其中一个点必然不被标记),减去x,并且不为负数(和0取max)
//退出循环判断:从起点和终点里取最小的(不然其中一个点必然不被标记),并和110-x取最小值(不然最大值就超出数据范围了),如果i大于这个值,则退出循环
{
memset(visit,0,sizeof(visit));
dfs(1,1,i,x+i);//i为最小值,x+i为最大值
if(visit[n][n])//如果终点被标记,则返回true
return true;
}
return false;//若所有区间均尝试过仍没有返回,则返回false
}
int main()
{
read(n);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
read(m[i][j]);
int l=0,r=N;//二分模板
while(l<=r)
{
int mid=l+r>>1;
if(check(mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("%d",ans);
return 0;
}

 评论

载入天数...载入时分秒...


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Material X 作为主题 , 总访问量为 次 。