题面描述

给定一个由字符 '0'（空地）、'1'（银矿）、'2'（金矿）组成的地图。矿堆只能由上下左右相邻的金矿或银矿连接形成。地图外的区域视为空地。

银矿的价值为 1，金矿的价值为 2。请找出地图中价值最大的矿堆，并输出该矿堆的总价值。

思路

$BFS$,直接对每一堆矿石广搜一遍取最大值即可

具体步骤如下：

1. 遍历网格：从左上角开始，遍历每一个位置。
2. 发现矿堆：当遇到一个 '1' 或 '2' 且未被访问过的格子时，使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历整个连通分量。
3. 计算价值：在遍历过程中，累加每个矿的价值（'1' 为1，'2' 为2）。
4. 更新最大值：比较当前连通分量的总价值与已记录的最大值，更新最大值。
5. 输出结果：遍历完所有格子后，输出最大的矿堆总价值。

cpp

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

// 定义方向数组，上下左右四个方向
const int DIRS = 4;
int dx[DIRS] = {-1, 1, 0, 0};
int dy[DIRS] = {0, 0, -1, 1};

int main(){
    // 读取输入，存储为字符串数组
    vector<string> grid;
    string line;
    while(getline(cin, line)){
        if(line.empty()) break;
        grid.push_back(line);
    }
    if(grid.empty()){
        cout << 0;
        return 0;
    }
    int n = grid.size();
    int m = grid[0].size();
    // 创建访问数组，初始化为未访问
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int max_value = 0;
    // 遍历每个格子
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            // 如果当前格子是矿且未被访问
            if((grid[i][j] == '1' || grid[i][j] == '2') && !visited[i][j]){
                // BFS 队列
                queue<pair<int,int>> q;
                q.push({i,j});
                visited[i][j] = true;
                int current_value = 0;
                // 计算当前连通分量的价值
                while(!q.empty()){
                    auto [x, y] = q.front(); q.pop();
                    if(grid[x][y] == '1') current_value += 1;
                    else if(grid[x][y] == '2') current_value += 2;
                    // 遍历四个方向
                    for(int d=0; d<DIRS; d++){
                        int nx = x + dx[d];
                        int ny = y + dy[d];
                        // 检查边界
                        if(nx >=0 && nx < n && ny >=0 && ny < m){
                            if((grid[nx][ny] == '1' || grid[nx][ny] == '2') && !visited[nx][ny]){
                                visited[nx][ny] = true;
                                q.push({nx, ny});
                            }
                        }
                    }
                }
                // 更新最大价值
                if(current_value > max_value){
                    max_value = current_value;
                }
            }
        }
    }
    // 输出结果
    cout << max_value;
}

python

from collections import deque
import sys

def main():
    # 读取输入，存储为列表
    grid = []
    for line in sys.stdin:
        line = line.strip()
        if not line:
            break
        grid.append(line)
    if not grid:
        print(0)
        return
    n = len(grid)
    m = len(grid[0])
    # 创建访问数组
    visited = [[False for _ in range(m)] for _ in range(n)]
    max_value = 0
    # 定义四个方向
    directions = [(-1,0),(1,0),(0,-1),(0,1)]
    # 遍历每个格子
    for i in range(n):
        for j in range(m):
            if (grid[i][j] == '1' or grid[i][j] == '2') and not visited[i][j]:
                q = deque()
                q.append((i,j))
                visited[i][j] = True
                current_value = 0
                while q:
                    x, y = q.popleft()
                    if grid[x][y] == '1':
                        current_value += 1
                    elif grid[x][y] == '2':
                        current_value += 2
                    # 遍历四个方向
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < n and 0 <= ny < m:
                            if (grid[nx][ny] == '1' or grid[nx][ny] == '2') and not visited[nx][ny]:
                                visited[nx][ny] = True
                                q.append((nx, ny))
                # 更新最大价值
                if current_value > max_value:
                    max_value = current_value
    # 输出结果
    print(max_value)

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 读取输入，存储为列表
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        List<String> gridList = new ArrayList<>();
        String line;
        while ((line = br.readLine()) != null && !line.trim().isEmpty()) {
            gridList.add(line.trim());
        }
        if(gridList.isEmpty()){
            System.out.println(0);
            return;
        }
        int n = gridList.size();
        int m = gridList.get(0).length();
        String[] grid = gridList.toArray(new String[0]);
        // 创建访问数组
        boolean[][] visited = new boolean[n][m];
        int maxValue = 0;
        // 定义四个方向
        int[][] directions = { {-1,0}, {1,0}, {0,-1}, {0,1} };
        // 遍历每个格子
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if( (grid[i].charAt(j) == '1' || grid[i].charAt(j) == '2') && !visited[i][j]){
                    // BFS 队列
                    Queue<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{i,j});
                    visited[i][j] = true;
                    int currentValue = 0;
                    while(!queue.isEmpty()){
                        int[] pos = queue.poll();
                        int x = pos[0];
                        int y = pos[1];
                        if(grid[x].charAt(y) == '1') currentValue += 1;
                        else if(grid[x].charAt(y) == '2') currentValue += 2;
                        // 遍历四个方向
                        for(int[] dir : directions){
                            int nx = x + dir[0];
                            int ny = y + dir[1];
                            if(nx >=0 && nx < n && ny >=0 && ny < m){
                                if( (grid[nx].charAt(ny) == '1' || grid[nx].charAt(ny) == '2') && !visited[nx][ny]){
                                    visited[nx][ny] = true;
                                    queue.offer(new int[]{nx, ny});
                                }
                            }
                        }
                    }
                    // 更新最大价值
                    if(currentValue > maxValue){
                        maxValue = currentValue;
                    }
                }
            }
        }
        // 输出结果
        System.out.println(maxValue);
    }
}

题目内容

给你一个由 '$0$' (空地)、'$1$' (银矿)、'$2$'(金矿) 组成的的地图，矿堆只能由上下左右相邻的金矿或银矿连接形成。

超出地图范围可以认为是空地。

假设银矿价值 $1$，金矿价值 $2$ ，请你找出地图中最大价值的矿堆并输出该矿堆的价值。

输入描述

地图元素信息如：

22220
00000
00000
11111

• 地图范围最大 $300*300$
• $0 ≤$ 地图元素 $≤ 2$

输出描述

矿堆的最大价值

样例1

输入

22220
00000
00000
01111

输出

8

样例2

输入

22220
00020
00010
01111

输出

15

样例3

输入

20000
00020
00000
00111

输出

3