[矩阵扩散]

矩阵扩散

真题目录: 点击去查看

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)
}