Skip to content

11031: 【原1031】二哥在黄山

题目

题目描述

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

Description

二哥与女朋友到黄山旅行。他们在山上玩了一整天,发现天色已晚,该回家了。而突然又开始下起了雨,二哥的女朋友表示非常不爽:“都是你搞的,早知道就不和你来了。”

二哥当然不能抛下女朋友不管,并且二哥也不想露宿在山上。于是他摊开被雨淋湿的地图。

黄山地图是一个N*N的矩阵,矩阵中的每一项表示那个地方的高度。二哥与女朋友处在左上角,他们的住处在右下角。在矩阵中可以朝上下左右走,但不能沿着对角线行走。二哥的女朋友不喜欢颠簸,所以二哥需要找到一条回到住处的路径,使得路径上的最高点与最低点之差尽量小,而不需要管这条路径有多长。

Input Format

第一行:N 接下来N行 N*N的整数矩阵,(\(0 \leq 每点的高度 \leq 110 \) )。 (\(2 \leq N \leq 100 \))

Output Format

一个整数,表示颠簸最小的路径中最高点与最低点的高度差。

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;
}