思路

两次BFS

• 第一次找出x,y所在的子网，将走过的元素置为2，并收集子网边缘的元素到edge队列中
• 从edge队列元素出发开始第二次BFS

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
    int x,y,m,n;
    cin >> x >> y >> n >> m;
    vector<vector<int>> graph(n + 1, vector<int>(m + 1, 0));
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> graph[i][j]; 
        }
    }


    queue<pair<int, int>> Q;
    queue<pair<int, int>> edge;

    // 找到目标x,y所在的子网，并收集边缘元素到edge,遍历过的元素值设置为2
    Q.push({x, y});
    graph[x][y] = 2;
    while (!Q.empty()) {
        int size = Q.size();
        for (int i = 0;i < size;i++) {
            pair<int, int>& current = Q.front();
            bool isEdge = false;
            Q.pop();
            for (int i = 0;i < 4;i++) {
                int newX = current.first + dir[i][0];
                int newY = current.second + dir[i][1];
                if (newX <= 0 || newX > m || newY <= 0 || newY >n || graph[newX][newY] == 2) continue;
                if (graph[newX][newY] == 0) {
                    if (!isEdge) {
                        edge.emplace(current.first, current.second);
                        isEdge = true;
                    }
                    continue;
                }
                graph[newX][newY] = 2;
                Q.emplace(newX, newY);
            }
        }
    }


    // 从边缘开始做BFS,每一次队列处理步数+1
    int step = 0;
    while (!edge.empty()) {
        int size = edge.size();
        step++;
        for (int i = 0;i < size;i++) {
            pair<int, int>& current = edge.front();
            edge.pop();
            for (int i = 0;i < 4;i++) {
                int newX = current.first + dir[i][0];
                int newY = current.second + dir[i][1];
                if (newX <= 0 || newX > m || newY <= 0 || newY > n || graph[newX][newY] == 2) continue;
                if (graph[newX][newY] == 1) {
                    cout << step - 1 << endl;
                    return 0;
                }
                graph[newX][newY] = 2; 
                edge.emplace(newX, newY);
            }
        }
    }

    cout << -1 << endl;
}

题目分析

塔子哥的农田受到地震的破坏，网点中有部分区域断开了联系。给定一个矩形农田，未被破坏的网点用 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;
}