牛客假日团队赛43：A tractor

英语好就先看题目：https://ac.nowcoder.com/acm/contest/5723/A
题目描述；
FJ有块农田太崎岖了，他要买一辆新拖拉机才能在这里巡视。这块农田由N x N个格子的非负整数表示高度(1<=N<=500)。拖拉机从当前格子走到相邻格子（东、南、西、北四个方向）的代价为高度差D，则FJ驶过这两个格子的拖拉机最少也要值D块钱。

FJ愿意花足够的钱买一辆新的拖拉机使得他能以最小的高度差走遍所有格子的一半(如果格子总数是奇数，那么一半的值为四舍五入的值)。因为FJ很懒，所以他找到你帮他编程计算他最小需要花多少钱买到符合这些要求的拖拉机
解题思路：
由于小的价值若能满足，大的价值更能满足了。可以二分寻找答案。枚举出发点(i,j)，dfs从出发点开始能在满足题意的情况下走多少个格子即可。里面有一些优化，比如只需要以图中最小的为l，最大的为r二分就好，再比如每次更换出发点去dfs，要不要每次都memset一遍vis数组呢？不用，如果从某个点(i1,j1)走完全部能走的点了，而且之后的某一个点(i2,j2)需要走(i1,j1)走过的点。但是在dfs(i1,j1)的时候已经把(i2,j2)开始的情况也走完了，因此这俩其实就是一个，故没有必要。
代码：

#include<bits/stdc++.h>
using namespace std;
int mp[510][510];
int n;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
int vis[510][510];
int dfs(int x,int y,int k)
{
    vis[x][y]=1;
    int res=1;
    for(int i=0;i<4;i++)
    {
        int xx=x+dir[i][0];
        int yy=y+dir[i][1];
        if(xx>0 && yy>0 && xx<=n && yy<=n && vis[xx][yy]==0 && abs(mp[xx][yy]-mp[x][y])<=k)
            res+=dfs(xx,yy,k);
    }
    return res;
}
bool check(int k)
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) {
            if(dfs(i,j,k)>=n*n/2)
                return 1;
        }
    return 0;
}
int bsearch(int l, int r)
{
    int ans;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}
int main()
{
    int l=0x3f3f3f3f ,r=0;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) {
            scanf("%d",&mp[i][j]);
            l = min(l, mp[i][j]);
            r = max(r, mp[i][j]);
        }
    int ans = bsearch(l, r);
    printf("%d\n", ans);
}