题目思路

思路：二分答案 + BFS

想要最大化 从 $(sx, sy)$ 到 $(tx, ty)$ 的所有路径中，和所有土豆最近的距离，假设我们设定距离为 $d$ ，则和任意一个土豆的距离小于 $d$ 的点都可以看成不可走的点。所以二分这个 $d$ ，然后 $check$ 是否满足要求。

单调性证明

如果 $d$ 满足，那么 $d - 1$ 必然满足，但是 $d + 1$ 不一定满足，所以这部分就具有单调性，那么通过二分答案来解决该问题就具有了正确性。

复杂度优化

现在的问题在于，如何快速获取一个点到所有土豆的距离中的最近距离?

一种显然的方式是从每个土豆都开始 $bfs$，最多有 $400$ 个土豆，总操作次数就是 $400 \times n\times m \approx 1e8$，这个是比较极限的。

但是可以通过建立一个虚拟源点，这个源点到所有土豆的距离为 $0$ ，图中任意两点的距离为曼哈顿距离，如此就又变成了单源 $bfs$，$bfs$ 中每个点只会被一个点更新，故求每个点到所有土豆的距离中的最近距离这部分，时间复杂度为 $O(nm)$

时间复杂度：$O(mm + nm\log (n+m))$

类似题目推荐

本题难度较大，请大家耐心练习！这里给大家推荐一些二分答案的题目!

LeetCode

1. 1631. 最小体力消耗路径

2. 778. 水位上升的泳池中游泳

3. 1162. 地图分析

Codefun2000

1. P1189. 华为实习 2023.04.12-实习笔试-第一题-购物系统的降级策略

2. P1106. 腾讯音乐 2023.3.23-第二题-划分字符串

3. P1006. 华为秋招 2022.9.21-数组取min

4. P1093. 米哈游 2023.03.19-第三题-塔子哥的无限字符串

5. P1086 携程 2023.3.16-二维矩阵可传送的最短路

代码

C++

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
const int INF = 0x3f3f3f3f;
int g[N][N];
int dist[N][N];
int vis[N][N];
int n, m, k;
int sx, sy, tx, ty;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
vector<pair<int, int>> q(N * N);

// check 即按照 mid 这个最近距离，任何到任意一个点的距离小于 mid 的点都不可到达
bool check(int mid) {
    int hh = 0, tt = -1;
    q[++tt] = {sx, sy};
    vis[sx][sy] = true;
    bool is_find = false;
    while (hh <= tt) {
        int x = q[hh].first, y = q[hh].second;
        hh += 1;
        // 上下左右四个方向遍历
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] >= mid && !vis[nx][ny]) {
                vis[nx][ny] = true;
                q[++tt] = {nx, ny};
                if (nx == tx && ny == ty) {
                    is_find = true;
                    break;
                }
            }
        }
        // 如果找到一条路径，提前退出，避免后续多余的搜索
        if (is_find) break;
    }

    bool ans = vis[tx][ty];
    // 将到达过的点全部标记为空，方便下一次遍历，无需清空整个数组
    for (int i = 0; i <= tt; ++i) vis[q[i].first][q[i].second] = false;
    return ans;
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            dist[i][j] = INF;

    int hh = 0, tt = -1;
    for (int a = 1; a <= k; ++a) {
        int x, y;
        scanf("%d%d", &x, &y);
        dist[x][y] = 0;
        q[++tt] = {x, y};
    }

    while (hh <= tt) {
        int x = q[hh].first, y = q[hh].second;
        hh += 1;
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1;
                q[++tt] = {nx, ny};
            }
        }
    }

    scanf("%d%d%d%d", &sx, &sy, &tx, &ty);

    // 二分答案，最大为 min(dist[sx][sy], dist[tx][ty])
    int l = 0, r = min(dist[sx][sy], dist[tx][ty]);
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    
    printf("%d\n", l);

    return 0;
}

python

N = 510
INF = 0x3f3f3f3f
g = [[0] * N for _ in range(N)]
dist = [[INF] * N for _ in range(N)]
vis = [[False] * N for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
q = [None] * (N * N)
n, m, k = map(int, input().split())

hh, tt = 0, -1
for a in range(1, k+1):
    x, y = map(int, input().split())
    dist[x][y] = 0
    tt += 1
    q[tt] = (x, y)

while hh <= tt:
    x, y = q[hh]
    hh += 1
    # 上下左右四个方向遍历
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 1 <= nx <= n and 1 <= ny <= m and dist[nx][ny] > dist[x][y] + 1:
            dist[nx][ny] = dist[x][y] + 1
            tt += 1
            q[tt] = (nx, ny)

sx, sy, tx, ty = map(int, input().split())

# check 即按照 mid 这个最近距离，任何到任意一个点的距离小于 mid 的点都不可到达
def check(mid):
    hh, tt = 0, -1
    tt += 1
    q[tt] = (sx, sy)
    vis[sx][sy] = True
    is_find = False
    while hh <= tt:
        x, y = q[hh]
        hh += 1
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 1 <= nx <= n and 1 <= ny <= m and dist[nx][ny] >= mid and not vis[nx][ny]:
                vis[nx][ny] = True
                tt += 1
                q[tt] = (nx, ny)
                if nx == tx and ny == ty:
                    is_find = True
                    break
        # 如果找到一条路径，提前退出，避免后续多余的搜索
        if is_find:
            break
    ans = vis[tx][ty]
    # 将到达过的点全部标记为空，方便下一次遍历，无需清空整个数组
    for i in range(tt+1):
        vis[q[i][0]][q[i][1]] = False
    return ans


# 二分答案，最大为 min(dist[sx][sy], dist[tx][ty])
l, r = 0, min(dist[sx][sy], dist[tx][ty])
while l < r:
    mid = (l + r + 1) >> 1
    if check(mid):
        l = mid
    else:
        r = mid - 1

print(l)

Java

import java.util.*;

public class Main {
    private static final int N = 510;
    private static final int INF = 0x3f3f3f3f;
    private static int[][] g = new int[N][N];
    private static int[][] dist = new int[N][N];
    private static boolean[][] vis = new boolean[N][N];
    private static int n, m, k;
    private static int sx, sy, tx, ty;

    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, 1, 0, -1};
    private static int[][] q = new int[N * N][2];

    // check 即按照 mid 这个最近距离，任何到任意一个点的距离小于 mid 的点都不可到达
    private static boolean check(int mid) {
        int hh = 0, tt = -1;
        q[++tt] = new int[]{sx, sy};
        vis[sx][sy] = true;
        boolean is_find = false;
        while (hh <= tt) {
            int x = q[hh][0], y = q[hh][1];
            hh += 1;
            // 上下左右四个方向遍历
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] >= mid && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    q[++tt] = new int[]{nx, ny};
                    if (nx == tx && ny == ty) {
                        is_find = true;
                        break;
                    }
                }
            }
            // 如果找到一条路径，提前退出，避免后续多余的搜索
            if (is_find) break;
        }

        boolean ans = vis[tx][ty];
        // 将到达过的点全部标记为空，方便下一次遍历，无需清空整个数组
        for (int i = 0; i <= tt; ++i) vis[q[i][0]][q[i][1]] = false;
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i = 1; i <= n; ++i) {
            Arrays.fill(dist[i], INF);
        }

        int hh = 0, tt = -1;
        for (int a = 1; a <= k; ++a) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            dist[x][y] = 0;
            q[++tt] = new int[]{x, y};
        }

        while (hh <= tt) {
            int x = q[hh][0], y = q[hh][1];
            hh += 1;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dx[i], ny = y + dy[i];
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] > dist[x][y] + 1) {
                    dist[nx][ny] = dist[x][y] + 1;
                    q[++tt] = new int[]{nx, ny};
                }
            }
        }

        sx = sc.nextInt();
        sy = sc.nextInt();
        tx = sc.nextInt();
        ty = sc.nextInt();

        // 二分答案，最大为 min(dist[sx][sy], dist[tx][ty])
        int l = 0, r = Math.min(dist[sx][sy], dist[tx][ty]);
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }

        System.out.println(l);
    }
}

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

const N = 510
const INF = 0x3f3f3f3f

var (
	g              [N][N]int
	dist           [N][N]int
	vis            [N][N]bool
	q              [N * N]pair
	n, m           int
	k              int
	sx, sy, tx, ty int
)

type pair struct {
	first, second int
}

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

// check 即按照 mid 这个最近距离，任何到任意一个点的距离小于 mid 的点都不可到达
func check(mid int) bool {
	hh, tt := 0, 0
	q[tt] = pair{sx, sy}
	vis[sx][sy] = true
	isFind := false
	for hh <= tt {
		x, y := q[hh].first, q[hh].second
		hh += 1
		for i := 0; i < 4; i++ {
			nx, ny := x+dx[i], y+dy[i]
			if nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] >= mid && !vis[nx][ny] {
				vis[nx][ny] = true
				tt += 1
				q[tt] = pair{nx, ny}
				if nx == tx && ny == ty {
					isFind = true
					break
				}
			}
		}
		// 如果找到一条路径，提前退出，避免后续多余的搜索
		if isFind {
			break
		}
	}

	ans := vis[tx][ty]
	// 将到达过的点全部标记为空，方便下一次遍历，无需清空整个数组
	for i := 0; i <= tt; i++ {
		vis[q[i].first][q[i].second] = false
	}
	return ans
}

func main() {
	in := bufio.NewReader(os.Stdin)
	fmt.Fscan(in, &n)
	fmt.Fscan(in, &m)
	fmt.Fscan(in, &k)

	for i := 1; i <= n; i++ {
		for j := 1; j <= m; j++ {
			dist[i][j] = INF
		}
	}

	hh, tt := 0, -1
	for a := 1; a <= k; a++ {
		var x, y int
		fmt.Fscan(in, &x)
		fmt.Fscan(in, &y)
		dist[x][y] = 0
		tt += 1
		q[tt] = pair{x, y}
	}

	for hh <= tt {
		x, y := q[hh].first, q[hh].second
		hh += 1
		for i := 0; i < 4; i++ {
			nx, ny := x+dx[i], y+dy[i]
			if nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] > dist[x][y]+1 {
				dist[nx][ny] = dist[x][y] + 1
				tt += 1
				q[tt] = pair{nx, ny}
			}
		}
	}

	fmt.Fscan(in, &sx)
	fmt.Fscan(in, &sy)
	fmt.Fscan(in, &tx)
	fmt.Fscan(in, &ty)

	// 二分答案，最大为 min(dist[sx][sy], dist[tx][ty])
	l, r := 0, min(dist[sx][sy], dist[tx][ty])
	for l < r {
		mid := (l + r + 1) >> 1
		if check(mid) {
			l = mid
		} else {
			r = mid - 1
		}
	}

	fmt.Println(l)
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
    input += data;
    return;
});
process.stdin.on('end', () => {
    const lines = input.trim().split('\n');
    const N = 510;
    const INF = 0x3f3f3f3f;
    let g = [];
    let dist = [];
    let vis = [];
    let q = [];
    let n, m, k;
    let sx, sy, tx, ty;

    let dx = [-1, 0, 1, 0];
    let dy = [0, 1, 0, -1];

    // check 即按照 mid 这个最近距离，任何到任意一个点的距离小于 mid 的点都不可到达
    function check(mid) {
        let hh = 0, tt = -1;
        q[++tt] = [sx, sy];
        vis[sx][sy] = true;
        let isFind = false;
        while (hh <= tt) {
            let [x, y] = q[hh];
            hh += 1;
            for (let i = 0; i < 4; ++i) {
                let nx = x + dx[i], ny = y + dy[i];
                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] >= mid && !vis[nx][ny]) {
                    vis[nx][ny] = true;
                    q[++tt] = [nx, ny];
                    if (nx == tx && ny == ty) {
                        isFind = true;
                        break;
                    }
                }
            }
            // 如果找到一条路径，提前退出，避免后续多余的搜索
            if (isFind) break;
        }

        let ans = vis[tx][ty];
        // 将到达过的点全部标记为空，方便下一次遍历，无需清空整个数组
        for (let i = 0; i <= tt; ++i) vis[q[i][0]][q[i][1]] = false;
        return ans;
    }

    nmk = lines[0].split(' ').map(Number);
    n = nmk[0], m = nmk[1], k = nmk[2];

    for (let i = 1; i <= n; ++i) {
        g[i] = new Array(m + 1).fill(0);
        dist[i] = new Array(m + 1).fill(INF);
        vis[i] = new Array(m + 1).fill(false);
    }

    let hh = 0, tt = -1;
    for (let a = 1; a <= k; ++a) {
        let [x, y] = lines[a].split(' ').map(Number);
        dist[x][y] = 0;
        q[++tt] = [x, y];
    }

    while (hh <= tt) {
        let [x, y] = q[hh];
        hh += 1;
        for (let i = 0; i < 4; ++i) {
            let nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] > dist[x][y] + 1) {
                dist[nx][ny] = dist[x][y] + 1;
                q[++tt] = [nx, ny];
            }
        }
    }

    [sx, sy, tx, ty] = lines[lines.length - 1].split(' ').map(Number);

    // 二分答案，最大为 min(dist[sx][sy], dist[tx][ty])
    let l = 0, r = Math.min(dist[sx][sy], dist[tx][ty]);
    while (l < r) {
        let mid = (l + r + 1) >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    console.log(l);
});

题目描述：

小美是一个农民，他有一片 $n \times m$ 大小的田地，共 $n$ 行 $m$ 列，其中行和列都用从 $1$ 开始的整数编号，田地中有 $k$ 个格子中埋有土豆。我们记第 $a$ 行第 $b$ 列的格子为 $(a, b)$ 。小美现在位于 $(x1, y1)$ ，他想要移动到 $(x2, y2)$ 处去收菜，但是他不想阻碍自己土地里土豆的生长情况，所以他不想在移动过程中碰到土豆。

小美每次移动可以移动到与他所处格子的相邻的一格中，形式化地说，如果小美位于 $(x, y)$ ，则小美可以移动到 $(x-1, y)$ ， $(x+1, y)$ ， $(x, y-1)$ ， $(x, y+1)$ 的格子之一，但小美不能移动到田地之外。

小美想要在移动过程中，离这些土豆越远越好，而不是走最短路径。

这里定义两个格子之间的距离为曼哈顿距离，即格子 $(a, b)$ 和 $(c, d)$ 之间的距离是 $|a-c|+|b-d|$ 。

小美想知道，移动中与土豆之间距离的最小值最大可能是多少。

请注意，如果无论小美如何移动，都会进入一个有土豆的格子的话，这个最大可能值为 $0$ 。

输入描述

第一行三个整数 $n$， $m$ ， $k$ ，分别表示田地的行数，列数和土豆个数。

接下来 $k$ 行，每行两个整数 $p$ ， $q$ ，表示一个土豆放置在格子 $(p, q)$ 中。任意两土豆的放置位置不同。

接下来一行四个整数 $x1$ ， $y1$， $x2$ ， $y2$ ，表示小美的出发位置和目的位置。保证小美的出发位置和目的位置上没有土豆。

对于全部数据，

$1 \le n, m \le 500$ ，

$n \times m \ge 3$，

$1 \le k \le min\{n \times m-2, 400\}$ ，

$1 \le p, x1, x2 \le n$ ，

$1 \le q, y1, y2 \le m, (x1, y1) ≠ (x2, y2)$ ，

保证 $(x1, y1)$ 和 $(x2, y2)$ 中没有土豆，并且一个格子中最多放置一个土豆。

输出描述

输出一行一个整数，表示移动过程中与土豆之间距离的最小值的可能最大值。

样例

输入

5 6 2
2 1
2 3
1 1 5 1

输出

1