题目描述
给你一个由 '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地址
深度优先搜索-栈实现
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