(B卷,200分)- 寻找最大价值的矿堆(Java & JS & Python)

题目描述

给你一个由 '0' (空地)、'1' (银矿)、'2'(金矿) 组成的的地图,矿堆只能由上下左右相邻的金矿或银矿连接形成。超出地图范围可以认为是空地。

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

输入描述

地图元素信息如:

22220
00000
00000
11111

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

输出描述

矿堆的最大价值

用例

输入 22220
00000
00000
01111
输出 8
说明
输入 22220
00020
00010
01111
输出 15
说明
输入 20000
00020
00000
00111
输出 3
说明

题目解析

本题可以使用深度优先搜索解决。

首先,根据输入得到一个地图矩阵。

然后,定义一个visited集合,用于记录访问过的点的坐标,或者将访问过的点赋值为0,避免一些点被二次访问。

之后,开始遍历矩阵的每一个元素,如果

  • 该元素的值>0(代表有价值)
  • 该元素位置未被访问过

那么就可以从该点向上、下、左、右四个方向开始深搜,对于新点依旧按照上面规则判断是否可以继续深搜。


2023.05.25

经过测试,本题的深度优先搜索(递归实现)在地图矩阵达到50*50以上时就会发生栈内存溢出,因此本题可以使用深度优先搜索(栈实现)。

深度优先搜索的栈实现,非常类似于广度优先搜索,其实就是将广度优先搜索的队列结构,换成栈结构,具体区别可以看:

在线OJ地址

在线OJ – 寻找最大价值的矿堆

深度优先搜索-栈实现

Java算法源码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {
  // 地图矩阵
  static ArrayList<ArrayList<Integer>> matrix;

  // 记录地图矩阵的行数row,列数col
  static int row;
  static int col;

  // 上下左右,四个方向的偏移量
  static int[][] offsets = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    matrix = new ArrayList<>();

    // 假设存在空行作为输入截止条件
    //    while (sc.hasNextLine()) {
    //      String line = sc.nextLine();
    //
    //      // 由于本题没有说明输入截止条件,因此使用空行作为输入截止条件
    //      if ("".equals(line)) {
    //        System.out.println(getResult());
    //        break;
    //      } else {
    //        matrix.add(
    //            new ArrayList<>(
    //
    // Arrays.stream(line.split("")).map(Integer::parseInt).collect(Collectors.toList())));
    //      }
    //    }

    // 没有空行作为输入截止条件
    while (sc.hasNextLine()) {
      matrix.add(
          new ArrayList<>(
              Arrays.stream(sc.nextLine().split(""))
                  .map(Integer::parseInt)
                  .collect(Collectors.toList())));
    }

    System.out.println(getResult());
  }

  public static int getResult() {
    row = matrix.size();
    if (row == 0) return 0;

    col = matrix.get(0).size();

    // 记录最大矿堆价值
    int ans = 0;

    // 遍历矩阵元素
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        // 如果点(i,j)没有被访问过,且点(i,j)上有矿,则进入深搜
        if (matrix.get(i).get(j) > 0) {
          ans = Math.max(ans, dfs(i, j));
        }
      }
    }

    return ans;
  }

  public static int dfs(int i, int j) {
    int sum = matrix.get(i).get(j);
    matrix.get(i).set(j, 0);

    LinkedList<int[]> stack = new LinkedList<>();
    stack.add(new int[] {i, j});

    while (stack.size() > 0) {
      int[] pos = stack.removeLast();
      int x = pos[0], y = pos[1];

      for (int[] offset : offsets) {
        int newX = x + offset[0];
        int newY = y + offset[1];

        if (newX >= 0 && newX < row && newY >= 0 && newY < col && matrix.get(newX).get(newY) > 0) {
          sum += matrix.get(newX).get(newY);
          matrix.get(newX).set(newY, 0);
          stack.add(new int[] {newX, newY});
        }
      }
    }

    return sum;
  }
}

JS算法源码

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

void (async function () {
  // 地图矩阵
  const matrix = [];

  // 假设存在空行作为输入截止条件
  // while (true) {
  //   const line = await readline();

  //   if (line != "") {
  //     matrix.push([...(await readline())].map(Number));
  //   } else {
  //     break;
  //   }
  // }

  // 没有空行作为输入截止条件
  while (true) {
    try {
      matrix.push([...(await readline())].map(Number));
    } catch (error) {
      break;
    }
  }

  console.log(getResult(matrix));
})();

// 记录地图矩阵的行数row,列数col
let row, col;

function getResult(matrix) {
  // 记录地图矩阵的行数row
  row = matrix.length;
  if (row == 0) return 0;

  // 记录地图矩阵的列数col
  col = matrix[0].length;

  // 记录最大矿堆价值
  let ans = 0;

  // 遍历矩阵元素
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (matrix[i][j] > 0) {
        ans = Math.max(ans, dfs(i, j, matrix));
      }
    }
  }

  return ans;
}

// 上下左右,四个方向的偏移量
const offsets = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

function dfs(x, y, matrix) {
  let sum = matrix[x][y];
  matrix[x][y] = 0;

  const stack = [[x, y]];

  while (stack.length > 0) {
    const [x, y] = stack.pop();

    for (let offset of offsets) {
      const newX = x + offset[0];
      const newY = y + offset[1];

      if (
        newX >= 0 &&
        newX < row &&
        newY >= 0 &&
        newY < col &&
        matrix[newX][newY] > 0
      ) {
        sum += matrix[newX][newY];
        matrix[newX][newY] = 0;
        stack.push([newX, newY]);
      }
    }
  }

  return sum;
}

Python算法源码

# 上下左右,四个方向的偏移量
offsets = ((-1, 0), (1, 0), (0, -1), (0, 1))


# 广搜
def dfs(x, y, matrix, row, col):
    total = matrix[x][y]
    matrix[x][y] = 0

    stack = [[x, y]]

    while len(stack) > 0:
        x, y = stack.pop()

        for offset in offsets:
            newX = x + offset[0]
            newY = y + offset[1]

            if row > newX >= 0 and col > newY >= 0 and matrix[newX][newY] > 0:
                total += matrix[newX][newY]
                matrix[newX][newY] = 0
                stack.append([newX, newY])

    return total


# 算法入口
def getResult(matrix):
    # 记录地图矩阵的行数row
    row = len(matrix)

    if row == 0:
        return 0

    # 记录地图矩阵的行数col
    col = len(matrix[0])

    # 记录最大矿堆价值
    ans = 0

    # 遍历矩阵元素
    for i in range(row):
        for j in range(col):
            # 如果点(i,j)没有被访问过,且点(i,j)上有矿,则进入深搜
            if matrix[i][j] > 0:
                ans = max(ans, dfs(i, j, matrix, row, col))

    return ans


# 输入获取
matrix = []

# 假设存在空行作为输入截止条件
# while True:
#     line = input()
#
#     if line == "":
#         print(getResult(matrix))
#         break
#     else:
#         matrix.append(list(map(int, list(line))))

# 没有空行作为输入截止条件
while True:
    try:
        matrix.append(list(map(int, list(input()))))
    except:
        break
print(getResult(matrix))

并查集解法

Java算法源码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    ArrayList<ArrayList<Integer>> matrix = new ArrayList<>();

    // 假设存在空行作为输入截止条件
    //    while (sc.hasNextLine()) {
    //      String line = sc.nextLine();
    //
    //      // 由于本题没有说明输入截止条件,因此使用空行作为输入截止条件
    //      if ("".equals(line)) {
    //        System.out.println(getResult());
    //        break;
    //      } else {
    //        matrix.add(
    //            new ArrayList<>(
    //
    // Arrays.stream(line.split("")).map(Integer::parseInt).collect(Collectors.toList())));
    //      }
    //    }

    // 没有空行作为输入截止条件
    while (sc.hasNextLine()) {
      matrix.add(
          new ArrayList<>(
              Arrays.stream(sc.nextLine().split(""))
                  .map(Integer::parseInt)
                  .collect(Collectors.toList())));
    }

    System.out.println(getResult(matrix));
  }

  public static int getResult(ArrayList<ArrayList<Integer>> matrix) {
    int row = matrix.size();
    if (row == 0) return 0;

    int col = matrix.get(0).size();

    // 并查集
    UnionFindSet ufs = new UnionFindSet(row * col);

    // 只需要向下、向右合并即可,offsets就是向下、向右的偏移量
    int[][] offsets = {{1, 0}, {0, 1}};

    // 遍历矩阵元素
    for (int i = 0; i < row; i++) {
      for (int j = 0; j < col; j++) {
        if (matrix.get(i).get(j) > 0) {
          for (int[] offset : offsets) {
            int newI = i + offset[0];
            int newJ = j + offset[1];
            if (newI >= 0
                && newI < row
                && newJ >= 0
                && newJ < col
                && matrix.get(newI).get(newJ) > 0) {
              ufs.union(i * col + j, newI * col + newJ);
            }
          }
        }
      }
    }

    // worth的key就是每个连通分量的根,value就是该根的矿堆价值
    HashMap<Integer, Integer> worth = new HashMap<>();

    // 遍历每一个节点,找到他们的根,将每个节点的矿堆价值集中到根上
    for (int pos = 0; pos < row * col; pos++) {
      int i = pos / col;
      int j = pos % col;

      int fa = ufs.find(ufs.fa[pos]);
      worth.put(fa, worth.getOrDefault(fa, 0) + matrix.get(i).get(j));
    }

    // 选出最大价值的根
    return worth.values().stream().max((a, b) -> a - b).orElse(0);
  }
}

class UnionFindSet {
  int[] fa;

  public UnionFindSet(int n) {
    this.fa = new int[n];
    for (int i = 0; i < n; i++) this.fa[i] = i;
  }

  public int find(int x) {
    if (x != this.fa[x]) {
      return (this.fa[x] = this.find(this.fa[x]));
    }
    return x;
  }

  public void union(int x, int y) {
    int x_fa = this.find(x);
    int y_fa = this.find(y);

    if (x_fa != y_fa) {
      this.fa[y_fa] = x_fa;
    }
  }
}

JS算法源码

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

void (async function () {
  // 地图矩阵
  const matrix = [];

  // 假设存在空行作为输入截止条件
  // while (true) {
  //   const line = await readline();

  //   if (line != "") {
  //     matrix.push([...(await readline())].map(Number));
  //   } else {
  //     break;
  //   }
  // }

  // 没有空行作为输入截止条件
  while (true) {
    try {
      matrix.push([...(await readline())].map(Number));
    } catch (error) {
      break;
    }
  }

  console.log(getResult(matrix));
})();

function getResult(matrix) {
  // 记录地图矩阵的行数row
  const row = matrix.length;
  if (row == 0) return 0;

  // 记录地图矩阵的列数col
  const col = matrix[0].length;

  // 并查集
  const ufs = new UnionFindSet(row * col);

  // 只需要向下、向右合并即可,offsets就是向下、向右的偏移量
  const offsets = [
    [1, 0],
    [0, 1],
  ];

  // 遍历矩阵元素
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (matrix[i][j] > 0) {
        for (let [offsetI, offsetJ] of offsets) {
          const newI = i + offsetI;
          const newJ = j + offsetJ;

          if (
            newI >= 0 &&
            newI < row &&
            newJ >= 0 &&
            newJ < col &&
            matrix[newI][newJ] > 0
          ) {
            ufs.union(i * col + j, newI * col + newJ);
          }
        }
      }
    }
  }

  // worth的key就是每个连通分量的根,value就是该根的矿堆价值
  const worth = {};

  // 遍历每一个节点,找到他们的根,将每个节点的矿堆价值集中到根上
  for (let pos = 0; pos < row * col; pos++) {
    const i = Math.floor(pos / col);
    const j = pos % col;

    const fa = ufs.find(ufs.fa[pos]);

    if (!worth[fa]) worth[fa] = 0;
    worth[fa] += matrix[i][j];
  }

  // 选出最大价值的根
  return Math.max(...Object.values(worth));
}

class UnionFindSet {
  constructor(n) {
    this.fa = new Array(n).fill(0).map((_, i) => i);
  }

  find(x) {
    if (x !== this.fa[x]) {
      return (this.fa[x] = this.find(this.fa[x]));
    }
    return x;
  }

  union(x, y) {
    const x_fa = this.find(x);
    const y_fa = this.find(y);

    if (x_fa !== y_fa) {
      this.fa[y_fa] = x_fa;
    }
  }
}

Python算法源码

# 并查集
class UnionFindSet:
    def __init__(self, n):
        self.fa = [idx for idx in range(n)]

    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]
        return x

    def union(self, x, y):
        x_fa = self.find(x)
        y_fa = self.find(y)

        if x_fa != y_fa:
            self.fa[y_fa] = x_fa


# 算法入口
def getResult(matrix):
    # 记录地图矩阵的行数row
    row = len(matrix)

    if row == 0:
        return 0

    # 记录地图矩阵的行数col
    col = len(matrix[0])

    # 并查集
    ufs = UnionFindSet(row * col)

    # 只需要向下、向右合并即可,offsets就是向下、向右的偏移量
    offsets = ((1, 0), (0, 1))

    # 遍历矩阵元素
    for i in range(row):
        for j in range(col):
            if matrix[i][j] > 0:
                for offsetI, offsetJ in offsets:
                    newI = i + offsetI
                    newJ = j + offsetJ

                    if row > newI >= 0 and col > newJ >= 0 and matrix[newI][newJ] > 0:
                        ufs.union(i * col + j, newI * col + newJ)

    # worth的key就是每个连通分量的根,value就是该根的矿堆价值
    worth = {}

    # 遍历每一个节点,找到他们的根,将每个节点的矿堆价值集中到根上
    for pos in range(row * col):
        i = pos // col
        j = pos % col

        fa = ufs.find(ufs.fa[pos])

        worth.setdefault(fa, 0)
        worth[fa] += matrix[i][j]

    # 选出最大价值的根
    return max(worth.values())


# 输入获取
matrix = []

# 假设存在空行作为输入截止条件
# while True:
#     line = input()
#
#     if line == "":
#         print(getResult(matrix))
#         break
#     else:
#         matrix.append(list(map(int, list(line))))

# 没有空行作为输入截止条件
while True:
    try:
        matrix.append(list(map(int, list(input()))))
    except:
        break

print(getResult(matrix))

免责声明:

1、IT资源小站为非营利性网站,全站所有资料仅供网友个人学习使用,禁止商用
2、本站所有文档、视频、书籍等资料均由网友分享,本站只负责收集不承担任何技术及版权问题
3、如本帖侵犯到任何版权问题,请立即告知本站,本站将及时予与删除下载链接并致以最深的歉意
4、本帖部分内容转载自其它媒体,但并不代表本站赞同其观点和对其真实性负责
5、一经注册为本站会员,一律视为同意网站规定,本站管理员及版主有权禁止违规用户
6、其他单位或个人使用、转载或引用本文时必须同时征得该帖子作者和IT资源小站的同意
7、IT资源小站管理员和版主有权不事先通知发贴者而删除本文

0

评论0

站点公告

没有账号?注册  忘记密码?