# 11031: 【原1031】二哥在黄山

### 题目描述

author: ghostgold 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1031

## Sample Input

5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1


## Sample Output

2


## Source

USACO 2003 U S Open

## FineArtz's solution

/* 二哥在黄山 */
#include <iostream>
#include <queue>
using namespace std;

class Point{
public:
Point() = default;
Point(int xx, int yy) : x(xx), y(yy) {}
int x = 0, y = 0;
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, a[105][105];

bool check(int low, int high){
if (a[1][1] < low || a[1][1] > high || a[n][n] < low || a[n][n] > high)
return false;
bool v[105][105] = {0};
queue<Point> q;
Point now(1, 1), next;
q.push(now);
v[1][1] = true;
while (!q.empty()){
now = q.front();
q.pop();
for (int k = 0; k < 4; ++k){
next.x = now.x + dx[k];
next.y = now.y + dy[k];
if (next.x < 1 || next.x > n || next.y < 1 || next.y > n || v[next.x][next.y])
continue;
if (a[next.x][next.y] < low || a[next.x][next.y] > high)
continue;
if (next.x == n && next.y == n)
return true;
q.push(next);
v[next.x][next.y] = true;
}
}
return false;
}

int main(){
cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cin >> a[i][j];
int r = 110, l = 0;
while (l < r){
int mid = (l + r) / 2;
bool flag = false;
for (int i = 0; i <= 110 - mid; ++i)
if (check(i, i + mid)){
flag = true;
break;
}
if (flag)
r = mid;
else
l = mid + 1;
}
cout << l << endl;
return 0;
}


## ligongzzz's solution

#include <iostream>
#include <cstring>
using namespace std;

int map_data[109][109] = { 0 };

int dx[] = { 0,1,0,-1 },
dy[] = { 1,0,-1,0 };
int n;

bool visited[109][109] = { 0 };
int max_h = 0;

bool dfs(int posx, int posy, int cur_max, int cur_min) {
visited[posx][posy] = true;
if (cur_max == -1) {
cur_max = cur_min = map_data[posx][posy];
}
else {
cur_max = map_data[posx][posy] > cur_max ? map_data[posx][posy] : cur_max;
cur_min = map_data[posx][posy] < cur_min ? map_data[posx][posy] : cur_min;
}
if (cur_max - cur_min > max_h) {
visited[posx][posy] = false;
return false;
}
if (posx == n - 1 && posy == n - 1)
return true;

for (int i = 0; i < 4; ++i) {
int nx = posx + dx[i], ny = posy + dy[i];
if (!visited[nx][ny] && nx >= 0 && nx < n && ny >= 0 && ny < n) {
auto flag = dfs(nx, ny, cur_max, cur_min);
if (flag) {
visited[posx][posy] = false;
return true;
}
}
}
visited[posx][posy] = false;
return false;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

cin >> n;

int h_min = 200, h_max = 0;

for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j) {
cin >> map_data[i][j];
h_min = map_data[i][j] < h_min ? map_data[i][j] : h_min;
h_max = map_data[i][j] > h_max ? map_data[i][j] : h_max;
}

int left = 0, right = h_max - h_min, right_ans = -1;

while (left <= right) {
auto mid = (left + right) >> 1;
max_h = mid;

memset(visited, 0, sizeof(visited));
if (dfs(0, 0, -1, -1)) {
right_ans = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}

cout << right_ans;

return 0;
}


## WashSwang's solution

#include <iostream>
using namespace std;
int A[101][101],n,queue[20000][2],head,tail,dir[4][2]={-1,0,1,0,0,-1,0,1};
bool visit[101][101];
void enqueue(int x,int y,int lowb,int upb)
{
int dx,dy;
for (int i=0;i<4;++i){
dx=dir[i][0];
dy=dir[i][1];
if (x+dx>=0&&x+dx<n&&y+dy>=0&&y+dy<n&&!visit[x+dx][y+dy]&&A[x+dx][y+dy]<=upb&&A[x+dx][y+dy]>=lowb){
queue[tail][0]=x+dx;
queue[tail][1]=y+dy;
visit[x+dx][y+dy]=true;
tail+=1;
}
}
}
int binarysearch(int low,int high)
{

int ans=0;
int l=low;
int r=high;
int mid;
bool flag;
while (l<=r)
{
mid=(l+r)/2;
flag=false;
for (int k=max(0,A[0][0]-mid);k<=min(A[0][0],A[n-1][n-1]);++k)
{
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
visit[i][j]=0;
queue[tail][0]=0;
queue[tail][1]=0;
visit[0][0]=true;
head=0;tail=1;
flag=false;
while (head!=tail)
{
int x=queue[head][0];
int y=queue[head][1];
head+=1;
if (x==n-1 && y==n-1)
{
flag=true;
break;
}
enqueue(x,y,k,k+mid);
}
if (flag) break;
}
if (flag){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
int high=0;
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
{
cin>>A[i][j];
if (A[i][j]>high)
high=A[i][j];
}
cout<<binarysearch(0,high);
return 0;
}


## yyong119's solution

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int MAX_N = 100;
const int m[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
int n, minh, maxh;
int map[MAX_N + 1][MAX_N + 1];
bool isVisited[MAX_N + 1][MAX_N + 1];
struct node {
int x, y;
};

bool findpath(const int& MIND, const int& MAXD) {

if (map[1][1] > MAXD || map[1][1] < MIND || map[n][n] > MAXD || map[n][n] < MIND) return false;

queue<node> que;
node now, next;
while (que.size()) que.pop();
memset(isVisited, false, sizeof(isVisited));
que.push({ 1, 1 });

while (!que.empty()) {
now = que.front(); que.pop();
isVisited[now.x][now.y] = true;
for (int i = 0; i < 4; ++i) {
next.x = now.x + m[i][0]; next.y = now.y + m[i][1];
if ((next.x > 0)&&(next.x <= n)&&(next.y > 0)&&(next.y <= n) && (!isVisited[next.x][next.y]) && (map[next.x][next.y] >= MIND) && (map[next.x][next.y] <= MAXD)) {
if ((next.x == n)&&(next.y == n)) return true;
que.push(next);
isVisited[next.x][next.y] = true;
}
}
}

return false;
}

int main() {

cin >> n;
minh = 120; maxh = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
cin >> map[i][j];
maxh = (map[i][j] > maxh) ? map[i][j] : maxh;
minh = (map[i][j] < minh) ? map[i][j] : minh;
}
int l = 0, r = maxh - minh;
while (l < r) {
int mid = (l + r) >> 1;
bool flag = false;
for (int i = minh; i <= maxh - mid; ++i)
if (findpath(i, i + mid)) {
flag = true;
break;
}
if (flag) r = mid; else l = mid + 1;
}
cout << l << endl;
return 0;
}