矩阵扩散

存在一个m*n的二维数组,其成员取值范围为0或1。其中值为1的成员具备扩散性,

每经过1S,将上下左右值为0的成员同化为1。

二维数组的成员初始值都为0,将第[i,j]和[k,l]两个位置上元素修改成1后,

求矩阵的所有元素变为1需要多长时间。

输入描述:

前两个数是矩阵m*n,中间两个数是第一个点的坐标,最后两个数是第二个点的坐标

其中这两个点初始为1,其他点初始为0

输出描述:

输出矩阵的所有元素变为1所需要秒数。

示例1:

输入

4,4,0,0,3,3

输出

3

let str = '4,4,0,0,3,3'
let strArr = str.split(',')
let m =parseInt(strArr[0]),n=parseInt(strArr[1])
let one1 = strArr[2],one2 = strArr[3]
let two1 = strArr[4],two2 = strArr[5]
let arr = []
for(let i=0;i<m;i++){
    let item = []
    for(let o=0;o<n;o++){
        item.push(0)
    }
    arr.push(item)
}
arr[one1][one2] = 1
arr[two1][two2] = 1
let time = 0
test()
console.log(time);

function test(){
    while (!checkOver()){
        let arr2 = JSON.parse(JSON.stringify(arr))
        for(let i=0;i<arr.length;i++){
            for(let o=0;o<arr[i].length;o++){
                if(arr[i][o]===1){
                    arr2[i][o]=1
                    // 上
                    if(i-1>=0){
                        arr2[i-1][o] = 1
                    }
                    // 下
                    if(i+1<=arr.length-1){
                        arr2[i+1][o] = 1
                    }
                    // 左
                    if(o-1>=0){
                        arr2[i][o-1] = 1
                    }
                    // 右
                    if(o+1<=arr[i].length-1){
                        arr2[i][o+1] = 1
                    }
                }
            }
        }
        arr = arr2
        time++
    }
}
function checkOver(){
    for(let i of arr){
        for(let o of i){
            if(o===0){
                return false
            }
        }
    }
    return true
}
机试题 文章被收录于专栏

某机试题,网上很少用js写的答案只有自己写了

全部评论
// 不管怎么样,四个角上,总有一个最后被扩散到,也就是最后一次扩散一定是到矩阵的四个角的某一个 // 这种思路对吗? ```java public static int spread2(int m, int n, int i, int j, int k, int l) { int[] arr = { Math.min(i + j, k + l), // 两个节点扩展到(0,0)最少需要的步数 Math.min(n - 1 - j + i, n - 1 - l + k), // 两个节点扩展到(0,n-1)最少需要的步数 Math.min(m - 1 - i + j, m - 1 - k + l), // 两个节点扩展到(m-1,0)最少需要的步数 Math.min(m - 1 - i + n - 1 - j, m - 1 - k + n - 1 - l) // 两个节点扩展到(m-1,n-1)最少需要的步数 }; int max = 0; for (int x = 0; x < arr.length; x++) { if (max < arr[x]) { max = arr[x]; } } return max; } ```
点赞 回复 分享
发布于 2023-06-04 03:48 浙江

相关推荐

点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务