Solution
和汽车拉力比赛差不多，思路都是二分，二分\(d\),但是汽车拉力比赛从一个路标开始搜即可，本题没有给定起点。一条合法路径起点是未知的，不得随便从一个点开始搜，否则可能找不到正确路径。
怎么处理呢？
容易想到对于每一个二分的\(d\)，开一个\(n^2\)的循环，从每一个点开始搜，如果从这个点搜满足，则return true。
暴力代码如下：
点击查看代码
bool check1(int d)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
memset(vis,INF,sizeof(vis));//每一次搜前清空
if(check(i,j,d)) return true; //以i,j作为起点搜
}
}
return false;
}
这样处理复杂度是很高的，一定会炸：
如何优化呢？
上述做法对于每一次二分的\(d\)都进行\(n^2\)暴力，我们发现，每一次\(n^2\)暴力\(d\)是唯一的，bfs都是在当前节点上尽可能的扩散。我们可以对每一个走过的点记录，如果这次bfs不行则下次bfs一定不能再走这个点，类似于记忆化搜索，可以理解为不能重蹈覆辙，因为如果走上了这个标记的点就一定不可行。（相当于把原来错误的道路又走了一遍，浪费时间）
如果文字很抽象，我们可以画图举例：
假设红色代表一次bfs，显然没有走过一半的点，那么下一次bfs就一定不能再走上红点，不然又进了死胡同，一定不行。
这样，我们不光剩下了每次搜索前的memset，还不用每个\((i,j)\)都作为起点搜(如果\((i,j)\)标记了显然不能作为起点)
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#define N 550
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> PAIR;
int n;
int mapp[N][N];
int vis[N][N];
double goal = 0;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
bool flg;
int minn = INF,maxn = -1;
bool check(int i,int j,int d)
{
double cnt=1;
queue <PAIR> q;
q.push(PAIR(i,j));
vis[i][j] = 1;
while(!q.empty())
{
PAIR p=q.front();
q.pop();
if(cnt >= goal)
{
return true;
}
for(int i=0;i<4;i++)
{
int ax = p.first + dx[i];
int ay = p.second + dy[i];
if(ax>=1&&ax<=n&&ay>=1&&ay<=n&&vis[ax][ay] == INF && abs(mapp[ax][ay]-mapp[p.first][p.second]) <= d)
{
cnt++;
q.push(PAIR(ax,ay));
vis[ax][ay] = vis[p.first][p.second]+1;
}
}
}
if(cnt >= goal) return true;
else return false;
}
bool check1(int d)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(vis[i][j]==INF)
{
if(check(i,j,d)) return true;
}
}
}
return false;
}
int main()
{
scanf("%d",&n);
goal = round(n*n*1.0/2); //四舍五入
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) scanf("%d",&mapp[i][j]),maxn = max(maxn,mapp[i][j]),minn = min(minn,mapp[i][j]);
}
int l = 1,r = INF;
while(l <= r)
{
memset(vis,INF,sizeof(vis));
int mid = (l+r)/2;
if(check1(mid)) r = mid-1;
else l = mid+1;
}
cout<<l<<endl;
return 0;
}