题目链接:http://nyoj.top/problem/306

  • 内存限制:64MB 时间限制:1000ms

题目描述

Dr.Kong设计的机器人卡多非常爱玩，它常常偷偷跑出实验室，在某个游乐场玩之不疲。这天卡多又跑出来了，在SJTL游乐场玩个不停，坐完碰碰车，又玩滑滑梯，这时卡多又走入一个迷宫。整个迷宫是用一个N * N的方阵给出，方阵中单元格中填充了一个整数，表示走到这个位置的难度。

这个迷宫可以向上走，向下走，向右走，向左走，但是不能穿越对角线。走迷宫的取胜规则很有意思，看谁能更快地找到一条路径，其路径上单元格最大难度值与最小难度值之差是最小的。当然了，或许这样的路径不是最短路径。

机器人卡多现在在迷宫的左上角（第一行，第一列）而出口在迷宫的右下角（第N行，第N列）。
卡多很聪明，很快就找到了这样的一条路径。你能找到吗？

输入描述

有多组测试数据，以EOF为输入结束的标志
第一行：N 表示迷宫是N*N方阵(2≤ N≤ 100)
接下来有N行，每一行包含N个整数，用来表示每个单元格中难度 (0≤任意难度≤120)。

输出描述

输出为一个整数，表示路径上最高难度与和最低难度的差。

样例输入

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

样例输出

2

解题思路

枚举路径上最高难度与和最低难度的差，判断在这个范围内能否到达终点。

普通枚举:

#include <bits/stdc++.h>
using namespace std;
int vis[105][105], mp[105][105], n, temp, min_, max_;
int arr[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void DFS(int x, int y) {
    if (mp[x][y] > max_ || mp[x][y] < min_)
        return ;
    vis[x][y] = 1;
    if (x == n - 1 && y == x) {
        temp = 1;
        return ;
    }
    for (int i = 0; i < 4; i++) {
        int tx = x + arr[i][0];
        int ty = y + arr[i][1];
        if (tx >= 0 && tx < n && ty >= 0 && ty < n && !vis[tx][ty]) {
            DFS(tx, ty);
            if (temp)
                return ;
        }
    }
}
bool mark(int l) {
    for (int i = 0; i + l <= 120; i++) {
        temp = 0;
        memset(vis, 0, sizeof(vis));
        min_ = i;
        max_ = i + l;
        DFS(0, 0);
        if (temp)
            return true;
    }
    return false;
}
int sovle(int l, int r) {
    for (int i = l; i <= r; i++)
        if (mark(i))
            return i;
}
int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &mp[i][j]);
        printf("%d\n", sovle(0, 120));
    }
    return 0;
}

二分枚举:

#include <bits/stdc++.h>
using namespace std;
int vis[105][105], mp[105][105], n, temp, min_, max_;
int arr[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
void DFS(int x, int y) {
    if (mp[x][y] > max_ || mp[x][y] < min_)
        return ;
    vis[x][y] = 1;
    if (x == n - 1 && y == x) {
        temp = 1;
        return ;
    }
    for (int i = 0; i < 4; i++) {
        int tx = x + arr[i][0];
        int ty = y + arr[i][1];
        if (tx >= 0 && tx < n && ty >= 0 && ty < n && !vis[tx][ty]) {
            DFS(tx, ty);
            if (temp)
                return ;
        }
    }
}
bool mark(int l) {
    for (int i = 0; i + l <= 120; i++) {
        temp = 0;
        memset(vis, 0, sizeof(vis));
        min_ = i;
        max_ = i + l;
        DFS(0, 0);
        if (temp)
            return true;
    }
    return false;
}
int sovle(int l, int r) {
    int mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (mark(mid))
            r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
int main() {
    while (~scanf("%d", &n)) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &mp[i][j]);
        printf("%d\n", sovle(0, 120));
    }
    return 0;
}