题目分析

塔子哥的农田受到地震的破坏，网点中有部分区域断开了联系。给定一个矩形农田，未被破坏的网点用 1 表示，破坏的网点用 0 表示，标记为 1 的相邻网点可以构成子网。塔子哥需要找到目标网点所在的子网，并计算离它最近的其他子网的最小距离。

思路

该题为力扣的改编题 1162. 地图分析

本题需要求当前区域到其他所有区域的最短 曼哈顿距离

我们分两次 BFS 来求出最短距离

• 第一次BFS的目的是标记不同的区域
• 第二次BFS的目的是求最短距离。

解题思路

整个问题可以通过两次广度优先搜索（BFS）来解决：

1. 第一次 BFS：用于标记目标网点所在的子网，同时将该子网的边缘元素收集起来，方便之后第二次 BFS 的执行。边缘元素是指目标子网中，与其他子网或空白区域（0）相邻的元素。
2. 第二次 BFS：从第一次收集的边缘元素出发，计算到其他子网的最短距离。只要找到第一个不同子网（即与目标子网不连通的子网），即可输出最短距离。

解题步骤

1. 输入数据处理：首先读取目标网点的坐标 (sx, sy)，农田的尺寸 n 和 m，以及农田的网点状态矩阵。
2. 第一次 BFS：标记子网：
   • 遍历矩阵，找到所有标记为 1 的网点，使用 BFS 遍历其连通的所有网点，并将这些网点标记为一个唯一的子网编号。
   • 如果目标网点 (sx, sy) 所在的网点被遍历到，记录下其所属的子网编号（即颜色）。
   • BFS 过程中收集目标子网的边缘网点，为第二次 BFS 做准备。
3. 第二次 BFS：计算最短距离：
   • 从第一次 BFS 收集的边缘网点出发，执行 BFS 遍历，找到距离最近的不同子网，并返回该距离。
   • 由于 BFS 本身是层次遍历的，因此一旦遇到不同的子网，当前的距离就是最小的。
4. 特殊情况处理：如果整个矩阵中只有一个子网，则输出 -1，因为此时不存在其他子网。

代码细节说明

1. 第一次 BFS 标记子网：通过 BFS 遍历所有网点，找到连通的 1，并将其标记为一个子网。每发现一个新的子网，就给它一个唯一的编号。
2. 第二次 BFS 寻找最短距离：从目标子网的所有边缘元素开始进行 BFS，层次遍历，找到第一个与目标子网不同的子网时，即输出当前的距离。
3. 特殊情况处理：如果只有一个子网，则直接输出 -1。

AC代码

Python

from collections import deque
sx, sy = map(int, input().split())
sx -= 1
sy -= 1
n, m = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n)]
idx = 2
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

# 第一次 BFS 遍历,标记不同的区域
def bfs(x, y, c):
    q = deque()
    q.append([x, y]) 
    g[x][y] = c
    while len(q):
        x, y = q.popleft()
        for i in range(4):
            a, b = x + dx[i], y + dy[i]
            if a < 0 or a >= n or b < 0 or b >= m or g[a][b] != 1:
                continue
            q.append([a, b])
            g[a][b] = c

for i in range(n):
    for j in range(m):
        if g[i][j] == 1:
            bfs(i, j, idx)
            idx += 1

# 如果只有陆地和海洋两种区域,则返回-1
if idx <= 3:
    print(-1)
else:
    color = g[sx][sy]
    q = deque()
    st = set()
    d = [[float('inf')] * m for _ in range(n)]

    # 第二次 BFS 遍历,找到最短距离
    for i in range(n):
        for j in range(m): 
            if g[i][j] == color:
                q.append([i, j])
                st.add((i, j))
                d[i][j] = 0
    res = 0
    while len(q):
        x, y = q.popleft()
        if g[x][y] != color and g[x][y]:
            res = d[x][y]
            break 
        for i in range(4):
            a, b = x + dx[i], y + dy[i]
            if a < 0 or a >= n or b < 0 or b >= m or (a, b) in st:
                continue
            q.append([a, b])
            d[a][b] = d[x][y] + 1
            st.add((a, b))
    print(res - 1)

Java

import java.util.*;

public class Main {
    private static int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static Deque<int[]> queue = new ArrayDeque<>();
    private static boolean[][] visited;

    // 第一次 DFS 遍历,标记不同的区域
    private static void infect(int[][] map, int m, int n, int i, int j) {
        if (i < 0 || i == m || j < 0 || j == n || map[i][j] != 1) {
            return;
        }
        map[i][j] = 2;
        visited[i][j] = true;
        queue.add(new int[]{i, j});
        infect(map, m, n, i - 1, j);
        infect(map, m, n, i + 1, j);
        infect(map, m, n, i, j - 1);
        infect(map, m, n, i, j + 1);
    }

    // 第二次 BFS 遍历,找到最短距离
    private static int minPath(int[][] map, int m, int n) {
        int step = 0;
        int cnt = 0, curLevel = queue.size(), nextLevel = queue.size();
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            cnt++;
            for (int[] direction : directions) {
                int i = cur[0] + direction[0], j = cur[1] + direction[1];
                if (i < 0 || i == m || j < 0 || j == n) {
                    continue;
                }
                if (map[i][j] == 1) {
                    return step;
                }
                if (!visited[i][j]) {
                    visited[i][j] = true;
                    queue.add(new int[]{i, j});
                    nextLevel++;
                }
            }
            if (cnt == curLevel) {
                curLevel = nextLevel;
                step++;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt() - 1, y = in.nextInt() -1 ;
        int m = in.nextInt(), n = in.nextInt();
        int[][] map = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = in.nextInt();
            }
        }
        // 第一次 DFS 遍历,标记 xy 所在的子网
        visited = new boolean[m][n];
        infect(map, m, n, x, y);
        System.out.println(minPath(map, m, n));
    }
}

C++

#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

const int INF = 2000;
vector<int> dx = {-1, 0, 1, 0};
vector<int> dy = {0, 1, 0, -1};

int main() {
    int sx, sy;
    cin >> sx >> sy;
    sx -= 1;
    sy -= 1;

    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> g[i][j];
        }
    }
    int idx = 2;
    // 第一次 BFS 遍历,标记不同的区域
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == 1) {
                queue<pair<int, int>> q;
                q.push({i, j});
                g[i][j] = idx;
                while (!q.empty()) {
                    int x = q.front().first;
                    int y = q.front().second;
                    q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int a = x + dx[k];
                        int b = y + dy[k];
                        if (a < 0 || a >= n || b < 0 || b >= m || g[a][b] != 1) continue;
                        q.push({a, b});
                        g[a][b] = idx;
                    }
                }
                idx++;
            }
        }
    }
    // 如果只有陆地和海洋两种区域,则返回-1
    if (idx <= 3) {
        cout << -1 << endl;
    } else {
        int color = g[sx][sy];
        queue<pair<int, int>> q;
        set<pair<int, int>> st;
        vector<vector<int>> d(n, vector<int>(m, INF));
        // 第二次 BFS 遍历,找到最短距离
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (g[i][j] == color) {
                    q.push({i, j});
                    st.insert({i, j});
                    d[i][j] = 0;
                }
            }
        }

        int res = 0;
        while (!q.empty()) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if (g[x][y] != color && g[x][y] != 0) {
                res = d[x][y];
                break;
            }
            for (int i = 0; i < 4; ++i) {
                int a = x + dx[i];
                int b = y + dy[i];
                if (a < 0 || a >= n || b < 0 || b >= m || st.count({a, b})) continue;
                q.push({a, b});
                d[a][b] = d[x][y] + 1;
                st.insert({a, b});
            }
        }

        cout << (res - 1) << endl;
    }

    return 0;
}

javaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
let queue = [];
let visited;

// 第一次 DFS 遍历，标记不同的区域
function infect(map, m, n, i, j) {
    if (i < 0 || i >= m || j < 0 || j >= n || map[i][j] !== 1) {
        return;
    }
    map[i][j] = 2;
    visited[i][j] = true;
    queue.push([i, j]);

    for (const [dx, dy] of directions) {
        infect(map, m, n, i + dx, j + dy);
    }
}

// 第二次 BFS 遍历，找到最短距离
function minPath(map, m, n) {
    let step = 0;
    let cnt = 0, curLevel = queue.length, nextLevel = queue.length;

    while (queue.length > 0) {
        let [x, y] = queue.shift();
        cnt++;

        for (const [dx, dy] of directions) {
            let i = x + dx, j = y + dy;
            if (i < 0 || i >= m || j < 0 || j >= n) {
                continue;
            }
            if (map[i][j] === 1) {
                return step;
            }
            if (!visited[i][j]) {
                visited[i][j] = true;
                queue.push([i, j]);
                nextLevel++;
            }
        }

        if (cnt === curLevel) {
            curLevel = nextLevel;
            step++;
        }
    }

    return -1;
}

// 读取输入并执行逻辑
async function main() {
    let firstLine = (await readline()).split(" ").map(Number);
    let x = firstLine[0] - 1, y = firstLine[1] - 1;
    
    let secondLine = (await readline()).split(" ").map(Number);
    let m = secondLine[0], n = secondLine[1];

    let map = [];
    for (let i = 0; i < m; i++) {
        map.push((await readline()).split(" ").map(Number));
    }

    // 初始化 visited 数组
    visited = Array.from({ length: m }, () => Array(n).fill(false));

    // 第一次 DFS 遍历，标记起点所在的区域
    infect(map, m, n, x, y);

    // 输出最短路径
    console.log(minPath(map, m, n));
    rl.close();
}

// 运行主函数
main();

问题描述

小明的农田受到地震的破坏，农田中的一些网点断开了联系。假设原本的农田网构成一个矩形，其中未被破坏的网点标记为 $1$，被破坏的网点标记为 $0$。标记为 $1$ 的网点连在一起构成一个子网。现在，小明需要找到一个目标网点，并找出离它最近的其他子网。请注意，两个网点相连只能通过上下左右四个方向，不可以通过斜对角相连。两个网点的距离定义为从一个网点（假设网点名为 $C$）到达另一个网点（假设网点名为 $D$）需要经过相连网点的最小数目（$C$ 和 $D$ 这两个网点不计算在内）。两个子网（假设分别为 $A$ 网和 $B$ 网）不相连，$A$ 网中所有的网点与 $B$ 网中所有的网点的距离中最小的那个即为 $A$ 网和 $B$ 网的最小距离。

输入格式

第一行包含两个正整数 $x, y$，表示目标网点的坐标位置（$x$ 表示行号，$y$ 表示列号）。

第二行包含两个正整数 $n, m$，表示农田矩形的行数 $n$ 和列数 $m$。

接下来的 $n$ 行每行包含 $m$ 个以空格分隔的整数 $0$ 或 $1$，表示农田网点的破坏情况。

输出格式

输出一个整数，表示最近的未被破坏子网的距离。如果整网中只有一个子网，则返回 $-1$。

样例输入

1 1
6 6
1 1 0 0 1 0
1 1 0 0 1 1
0 0 0 0 1 0
0 1 0 1 0 0
1 1 0 0 0 0
1 1 1 0 1 1

样例输出

1

评测数据与规模

• $1 \leq n, m \leq 1000$。
• 输入保证目标网点是未被破坏的网点，且目标网点所在子网是一个子网。