[矩阵扩散]
矩阵扩散
真题目录: 点击去查看
E 卷 100分题型
题目描述
存在一个m×n的二维数组，其成员取值范围为0或1。
其中值为1的成员具备扩散性，每经过1S，将上下左右值为0的成员同化为1。
二维数组的成员初始值都为0，将第[i,j]和[k,l]两个个位置上元素修改成1后，求矩阵的所有元素变为1需要多长时间。
输入描述
输入数据中的前2个数字表示这是一个m×n的矩阵，m和n不会超过1024大小；
中间两个数字表示一个初始扩散点位置为i,j；
最后2个数字表示另一个扩散点位置为k,l。
输出描述
输出矩阵的所有元素变为1所需要秒数。
用例1
输入
4,4,0,0,3,3
输出
3
说明
输入数据中的前2个数字表示这是一个4*4的矩阵；中间两个数字表示一个初始扩散点位置为0,0；最后2个数字表示另一个扩散点位置为3,3。给出的样例是一个简单模型，初始点在对角线上，达到中间的位置分别为3次迭代，即3秒。所以输出为3。
题解
思路：
- 多源bfs(模板题，可以背一下)
c++
#include<iostream>
#include<vector>
#include<string>
#include <utility>
#include <sstream>
#include<algorithm>
#include<queue>
using namespace std;
// 通用 split 函数
vector<string> split(const string& str, const string& delimiter) {
vector<string> result;
size_t start = 0;
size_t end = str.find(delimiter);
while (end != string::npos) {
result.push_back(str.substr(start, end - start));
start = end + delimiter.length();
end = str.find(delimiter, start);
}
// 添加最后一个部分
result.push_back(str.substr(start));
return result;
}
int main() {
string s;
cin >> s;
// 处理输入
vector<string> ans = split(s, ",");
int m = stoi(ans[0]);
int n = stoi(ans[1]);
int x1 = stoi(ans[2]);
int y1 = stoi(ans[3]);
int x2 = stoi(ans[4]);
int y2 = stoi(ans[5]);
vector<vector<int>> matrix(m , vector<int>(n, 0));
matrix[x1][y1] = 1;
matrix[x2][y2] = 1;
// 定义方向
int direct[2][4] = {
{1, 0, -1, 0},
{0, 1, 0, -1}
};
queue<pair<int,int>> q;
q.push({x1,y1});
q.push({x2,y2});
int count = 0;
// bfs 使用队列模拟
while (!q.empty()) {
queue<pair<int,int>> tmp;
while (!q.empty()) {
pair<int, int> p = q.front();
q.pop();
int x = p.first;
int y = p.second;
for (int i = 0; i < 4; i++) {
int x1 =x + direct[0][i];
int y1 = y + direct[1][i];
if (x1 < 0 || x1 >= m || y1 < 0 || y1 >= n) {
continue;
}
if ( matrix[x1][y1] == 1) {
continue;
}
matrix[x1][y1] = 1;
tmp.push({x1, y1});
}
}
count++;
q = tmp;
}
cout << count - 1;
return 0;
}
JAVA
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Integer[] arr =
Arrays.stream(sc.next().split(",")).map(Integer::parseInt).toArray(Integer[]::new);
System.out.println(getResult(arr[0], arr[1], arr[2], arr[3], arr[4], arr[5]));
}
/**
* @param m m m×n的二维数组
* @param n n m×n的二维数组
* @param i 扩散点位置为i,j
* @param j 扩散点位置为i,j
* @param k 扩散点位置为k,l
* @param l 扩散点位置为k,l
* @return 扩散所有点需要的时间
*/
public static int getResult(int m, int n, int i, int j, int k, int l) {
int[][] matrix = new int[m][n];
matrix[i][j] = 1;
matrix[k][l] = 1;
// count记录未被扩散的点的数量
int count = m * n - 2;
// 多源BFS实现队列
LinkedList<int[]> queue = new LinkedList<>();
queue.addLast(new int[] {i, j});
queue.addLast(new int[] {k, l});
// 上下左右偏移量
int[][] offsets = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int day = 0;
// 如果扩散点没有了，或者所有点已被扩散，则停止循环
while (queue.size() > 0 && count > 0) {
LinkedList<int[]> newQueue = new LinkedList<>();
for (int[] pos : queue) {
int x = pos[0];
int y = pos[1];
for (int[] offset : offsets) {
int newX = x + offset[0];
int newY = y + offset[1];
if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] == 0) {
// 将点被扩散的时间记录为该点的值
matrix[newX][newY] = 1;
// 被扩散到的点将变为新的扩散源
newQueue.addLast(new int[] {newX, newY});
// 未被扩散点的数量--
count--;
}
}
}
queue = newQueue;
day++;
}
return day;
}
}
Python
# 输入获取
m, n, i, j, k, l = map(int, input().split(","))
# 算法入口
def getResult(m, n, i, j, k, l):
"""
:param m: 矩阵行数
:param n: 矩阵列数
:param i: 扩散点1行号
:param j: 扩散点1列好
:param k: 扩散点2行号
:param l: 扩散点2列号
:return: 矩阵的所有元素变为1所需要秒数
"""
matrix = [[0 for _ in range(n)] for _ in range(m)]
matrix[i][j] = 1
matrix[k][l] = 1
# count记录未被扩散的点的数量
count = m * n - 2
# 多源BFS实现队列
queue = [[i, j], [k, l]]
# 上下左右偏移量
offsets = ((1, 0), (-1, 0), (0, 1), (0, -1))
day = 0
# 如果扩散点没有了，或者所有点已被扩散，则停止循环
while len(queue) > 0 and count > 0:
newQueue = []
for x, y in queue:
for offsetX, offsetY in offsets:
newX = x + offsetX
newY = y + offsetY
if 0 <= newX < m and 0 <= newY < n and matrix[newX][newY] == 0:
# 将点被扩散的时间记录为该点的值
matrix[newX][newY] = 1
# 被扩散到的点将变为新的扩散源
newQueue.append([newX, newY])
# 未被扩散点的数量--
count -= 1
queue = newQueue
day += 1
return day
# 算法调用
print(getResult(m, n, i, j, k, l))
JavaScript
/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
rl.on("line", (line) => {
const [m, n, i, j, k, l] = line.split(",").map(Number);
console.log(getResult(m, n, i, j, k, l));
});
/**
* @param {*} m m×n的二维数组
* @param {*} n m×n的二维数组
* @param {*} i 扩散点位置为i,j
* @param {*} j 扩散点位置为i,j
* @param {*} k 扩散点位置为k,l
* @param {*} l 扩散点位置为k,l
*/
function getResult(m, n, i, j, k, l) {
const matrix = new Array(m).fill(0).map(() => new Array(n).fill(0));
matrix[i][j] = 1;
matrix[k][l] = 1;
// count记录未被扩散的点的数量
let count = m * n - 2;
// 多源BFS实现队列
let queue = [
[i, j],
[k, l],
];
// 上下左右偏移量
const offsets = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
let day = 0;
// 如果扩散点没有了，或者所有点已被扩散，则停止循环
while (queue.length > 0 && count > 0) {
const newQueue = [];
for (const [x, y] of queue) {
for (let [offsetX, offsetY] of offsets) {
const newX = x + offsetX;
const newY = y + offsetY;
if (
newX >= 0 &&
newX < m &&
newY >= 0 &&
newY < n &&
matrix[newX][newY] == 0
) {
// 将点被扩散的时间记录为该点的值
matrix[newX][newY] = 1;
// 被扩散到的点将变为新的扩散源
newQueue.push([newX, newY]);
// 未被扩散点的数量--
count--;
}
}
}
queue = newQueue;
day++;
}
return day;
}
Go
package main
import (
"fmt"
"strconv"
"strings"
)
func main() {
var input string
fmt.Scan(&input)
// 处理输入
parts := strings.Split(input, ",")
m, _ := strconv.Atoi(parts[0])
n, _ := strconv.Atoi(parts[1])
x1, _ := strconv.Atoi(parts[2])
y1, _ := strconv.Atoi(parts[3])
x2, _ := strconv.Atoi(parts[4])
y2, _ := strconv.Atoi(parts[5])
// 初始化矩阵
matrix := make([][]int, m)
for i := range matrix {
matrix[i] = make([]int, n)
}
matrix[x1][y1] = 1
matrix[x2][y2] = 1
directions := [][2]int{
{1, 0},
{0, 1},
{-1, 0},
{0, -1},
}
// 初始化队列
queue := [][2]int{{x1, y1}, {x2, y2}}
count := 0
// BFS 使用队列模拟
for len(queue) > 0 {
newQueue := [][2]int{}
for _, p := range queue {
x, y := p[0], p[1]
for _, d := range directions {
nx, ny := x+d[0], y+d[1]
if nx < 0 || nx >= m || ny < 0 || ny >= n {
continue
}
if matrix[nx][ny] == 1 {
continue
}
matrix[nx][ny] = 1
newQueue = append(newQueue, [2]int{nx, ny})
}
}
count++
queue = newQueue
}
fmt.Println(count - 1)
}
原文地址：https://blog.csdn.net/qq_45776114/article/details/145302931
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！