# 题目：2023B-寻找价值最大的矿堆
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：BFS
# 代码看不懂的地方，请直接在群上提问


from collections import deque

# 表示四个方向的数组
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]

# 输入地图
grid = list()
while True:
    try:
        row = input()
        if len(row) == 0:
            break
        grid.append(row)
    except:
        break


# 根据地图获得行数、列数
n, m = len(grid), len(grid[0])

# 答案变量，用于记录价值最大的矿堆
ans = 0
# 用于检查的二维矩阵
# 0表示没检查过，1表示检查过了
check_list = [[0] * m for _ in range(n)]

# 最外层的大的双重循环，是用来找BFS的起始搜索位置的
for i in range(n):
    for j in range(m):
        # 找到一个"1"或"2"，并且这个点从未被搜索过：那么可以进行BFS的搜索
        # 1. 值是"1"或"2"        2. 没被搜索过
        if grid[i][j] != "0" and check_list[i][j] == 0:
            # BFS的过程
            q = deque()
            q.append([i, j])        # BFS的起始点
            check_list[i][j] = 1
            cur_value = 0           # 初始化当前矿堆的价值为0
            while len(q) > 0:       # 当队列中还有元素时，持续地进行搜索
                qSize = len(q)
                for _ in range(qSize):
                    # 弹出队头元素，为当前点
                    x, y = q.popleft()
                    # 更新当前连通块的价值
                    cur_value += int(grid[x][y])
                    for dx, dy in DIRECTIONS:
                        nxt_x, nxt_y = x+dx, y+dy
                        # 若下一个点要加入队列，应该满足以下三个条件：
                        # 1.没有越界
                        # 2.在grid中值为"1"或"2"
                        # 3.尚未被检查过
                        if 0 <= nxt_x < n and 0 <= nxt_y < m:       # 越界判断
                            # 在grid中为"1"或"2"，尚未被检查过
                            if grid[nxt_x][nxt_y] != "0" and check_list[nxt_x][nxt_y] == 0:
                                q.append([nxt_x, nxt_y])        # 入队
                                check_list[nxt_x][nxt_y] = 1    # 标记为已检查过

            # BFS搜索完成，更新本连通块的价值
            ans = max(cur_value, ans)

print(ans)

Java

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    static int n, m;
    static String[] grid;
    static int[][] checkList;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        Queue<int[]> queue = new ArrayDeque<>();

        String line;
        StringBuilder input = new StringBuilder();
        while (scanner.hasNextLine() && !(line = scanner.nextLine()).isEmpty()) {
            input.append(line).append("\n");
        }
        String[] rows = input.toString().split("\n");

        n = rows.length;
        m = rows[0].length();
        grid = rows;
        checkList = new int[n][m];

        int ans = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if ((grid[i].charAt(j) != '0') && (checkList[i][j] == 0)) {
                    int curValue = 0;
                    queue.add(new int[]{i, j});
                    checkList[i][j] = 1;

                    while (!queue.isEmpty()) {
                        int qSize = queue.size();
                        for (int k = 0; k < qSize; k++) {
                            int[] point = queue.poll();
                            int x = point[0];
                            int y = point[1];
                            curValue += Character.getNumericValue(grid[x].charAt(y));

                            for (int[] dir : DIRECTIONS) {
                                int nxt_x = x + dir[0];
                                int nxt_y = y + dir[1];

                                if (nxt_x >= 0 && nxt_x < n && nxt_y >= 0 && nxt_y < m &&
                                        (grid[nxt_x].charAt(nxt_y) != '0') && checkList[nxt_x][nxt_y] == 0) {
                                    queue.add(new int[]{nxt_x, nxt_y});
                                    checkList[nxt_x][nxt_y] = 1;
                                }
                            }
                        }
                    }
                    ans = Math.max(ans, curValue);
                }
            }
        }
        System.out.println(ans);
    }
}

C++

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

int DIRECTIONS[][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int n, m;
vector<string> grid;
vector<vector<int>> checkList;

int main() {
    string line;
    while (getline(cin, line) && !line.empty()) {
        grid.push_back(line);
    }

    n = grid.size();
    m = grid[0].size();
    checkList.resize(n, vector<int>(m, 0));

    int ans = 0;
    queue<pair<int, int>> q;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] != '0' && checkList[i][j] == 0) {
                int curValue = 0;
                q.push({i, j});
                checkList[i][j] = 1;

                while (!q.empty()) {
                    int qSize = q.size();
                    for (int k = 0; k < qSize; k++) {
                        int x = q.front().first;
                        int y = q.front().second;
                        q.pop();
                        curValue += grid[x][y] - '0';

                        for (auto dir : DIRECTIONS) {
                            int nxt_x = x + dir[0];
                            int nxt_y = y + dir[1];

                            if (nxt_x >= 0 && nxt_x < n && nxt_y >= 0 && nxt_y < m &&
                                grid[nxt_x][nxt_y] != '0' && checkList[nxt_x][nxt_y] == 0) {
                                    q.push({nxt_x, nxt_y});
                                    checkList[nxt_x][nxt_y] = 1;
                            }
                        }
                    }
                }
                ans = max(ans, curValue);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

解法二：DFS

Python

# 题目：2023B-寻找价值最大的矿堆
# 分值：200
# 作者：闭着眼睛学数理化
# 算法：DFS
# 代码看不懂的地方，请直接在群上提问


# 表示四个方向的数组
DIRECTIONS = [(0,1), (1,0), (-1,0), (0,-1)]

# 输入地图
grid = list()
while True:
    try:
        row = input()
        if len(row) == 0:
            break
        grid.append(row)
    except:
        break

# 根据地图获得行数、列数
n, m = len(grid), len(grid[0])

# 答案变量，用于记录价值最大的矿堆
ans = 0
# 用于检查的二维矩阵
# 0表示没检查过，1表示检查过了
check_list = [[0] * m for _ in range(n)]

# 构建DFS递归函数
def dfs(check_list, x, y):
    # 声明变量cur_value为全局变量，表示当前DFS的矿堆价值
    global cur_value
    # 将点(x, y)标记为已检查过
    check_list[x][y] = 1
    # 更新当前连通块的价值
    cur_value += int(grid[x][y])
    for dx, dy in DIRECTIONS:
        nxt_x, nxt_y = x + dx, y + dy
        # 若下一个点继续进行dfs，应该满足以下三个条件：
        # 1.没有越界
        # 2.在grid中值为"1"或"2"
        # 3.尚未被检查过
        if 0 <= nxt_x < n and 0 <= nxt_y < m:       # 越界判断
            # 在grid中为"1"或"2"，尚未被检查过
            if grid[nxt_x][nxt_y] != "0" and check_list[nxt_x][nxt_y] == 0:
                # 可以进行dfs
                dfs(check_list, nxt_x, nxt_y)


# 最外层的大的双重循环，是用来找DFS的起始搜索位置的
for i in range(n):
    for j in range(m):
        # 找到一个"1"或"2"，并且这个"1"或"2"从未被搜索过：那么可以进行DFS的搜索
        # 1. 值得是"1"或"2"       2. 没被搜索过
        if grid[i][j] != "0" and check_list[i][j] == 0:
            # 初始化当前矿堆的价值为0
            cur_value = 0
            dfs(check_list, i, j)
            # DFS搜索完成，更新最大矿堆的价值
            ans = max(ans, cur_value)

print(ans)

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int[][] DIRECTIONS = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
    static int n, m;
    static List<String> grid = new ArrayList<>();
    static List<List<Integer>> checkList = new ArrayList<>();
    static int ans = 0;

    static void dfs(int x, int y, int[] curValue) {
        checkList.get(x).set(y, 1);
        curValue[0] += grid.get(x).charAt(y) - '0';

        for (int[] dir : DIRECTIONS) {
            int nxt_x = x + dir[0];
            int nxt_y = y + dir[1];

            if (nxt_x >= 0 && nxt_x < n && nxt_y >= 0 && nxt_y < m &&
                    grid.get(nxt_x).charAt(nxt_y) != '0' && checkList.get(nxt_x).get(nxt_y) == 0) {
                dfs(nxt_x, nxt_y, curValue);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine();
            if (line.isEmpty()) {
                break;
            }
            grid.add(line);
        }

        n = grid.size();
        m = grid.get(0).length();
        for (int i = 0; i < n; i++) {
            checkList.add(new ArrayList<>());
            for (int j = 0; j < m; j++) {
                checkList.get(i).add(0);
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid.get(i).charAt(j) != '0' && checkList.get(i).get(j) == 0) {
                    int[] curValue = {0};
                    dfs(i, j, curValue);
                    ans = Math.max(ans, curValue[0]);
                }
            }
        }
        System.out.println(ans);
    }
}

C++

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

int DIRECTIONS[][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int n, m;
vector<string> grid;
vector<vector<int>> checkList;
int ans = 0;

void dfs(int x, int y, int &curValue) {
    checkList[x][y] = 1;
    curValue += grid[x][y] - '0';

    for (auto dir : DIRECTIONS) {
        int nxt_x = x + dir[0];
        int nxt_y = y + dir[1];

        if (nxt_x >= 0 && nxt_x < n && nxt_y >= 0 && nxt_y < m &&
            grid[nxt_x][nxt_y] != '0' && checkList[nxt_x][nxt_y] == 0) {
                dfs(nxt_x, nxt_y, curValue);
        }
    }
}

int main() {
    string line;
    while (getline(cin, line) && !line.empty()) {
        grid.push_back(line);
    }

    n = grid.size();
    m = grid[0].size();
    checkList.resize(n, vector<int>(m, 0));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] != '0' && checkList[i][j] == 0) {
                int curValue = 0;
                dfs(i, j, curValue);
                ans = max(ans, curValue);
            }
        }
    }

    cout << ans << endl;
    return 0;
}

时空复杂度

时间复杂度：O(MN)。

空间复杂度：O(MN)。