問題來源

https://segmentfault.com/q/1010000013091395?_ea=3284779

問題描述：

存在一個0，1值的二維數(shù)組，給定一個坐標(biāo)[x,y]，如果該坐標(biāo)所代表的元素值為1，則返回該坐標(biāo)所代表的元素相鄰的所有值為1的元素坐標(biāo)。

解題思路

對于這種查找元素這類題目，腦袋里的第一個想法就是應(yīng)該使用遍歷。然后選擇使用何種遍歷，由于這個查找元素是跟位置有關(guān)的，所以使用寬度遍歷（寬度遍歷的定義）最合適。

寬度遍歷：寬度優(yōu)先遍歷，是以離初態(tài)距離為序進(jìn)行遍歷。

解題方案

初始化定義：

• queue: 一個臨時的緩存隊列，存儲臨時匹配的結(jié)果
• result： 一個結(jié)果數(shù)組，存儲所有的匹配結(jié)果
• memo：一個原數(shù)組的元素的記憶數(shù)組，如果存在記憶為true，初始值全為false

// 定義一個遍歷數(shù)組
var arr =[
    [0,0,0,0,0,0,0,0,0,0,0], 
    [0,0,0,0,0,0,0,0,0,0,0], 
    [0,0,0,0,0,0,0,0,0,0,0], 
    [0,0,0,0,1,0,0,0,1,0,0], 
    [0,0,0,0,1,0,0,0,1,0,0],
    [0,0,0,0,1,0,0,0,1,0,0],
    [0,0,0,0,1,0,0,0,0,0,0],
    [0,0,0,0,1,0,0,0,0,0,0],
    [0,0,0,0,1,1,1,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0],
]

// 聲明一個遍歷方法
function fn ([x, y]) {
    // 定義一個緩存隊列queue，存儲臨時匹配的結(jié)果
    const queue = []
    // 定義一個result，存儲所有的匹配結(jié)果
    const result = []
    // 定義一個原數(shù)組的元素的記憶數(shù)組，初始值為false，如果原數(shù)組的元素元素存在則記憶值變?yōu)閠rue，
    const memo = arr.map(row => new Array(row.length).fill(false))
    // 定義一個方向數(shù)組，它的元素值分別表示左、右、上、下
    const direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    // 如果指定位置元素值不為1，直接返回false，跳出查詢函數(shù);
    // 如果存在，則將位置結(jié)果推入臨時數(shù)組queue，和結(jié)果數(shù)組result
    if (arr[x][y] !== 1) {
        return false
    } else {
        queue.push([x, y])
        result.push([x, y])
    }

    // 臨時存儲結(jié)果數(shù)組中是否有元素，如果有，則進(jìn)行循環(huán)；如果沒有，則跳出while循環(huán)，執(zhí)行其它語句
    while(queue.length > 0) {
        // 從緩存隊列中取出存在元素的坐標(biāo)
        const [x, y] = queue.pop()
        // 查找該坐標(biāo)位置左右上下位置值為1的元素，如果存在且記憶數(shù)組沒有記憶過該元素，那么就將用memo記憶該元素，
        // 然后推入臨時數(shù)組queue和結(jié)果數(shù)組，然后結(jié)束本次循環(huán)，接著返回循環(huán)條件判斷，看是否接著執(zhí)行循環(huán)，如果執(zhí)行條件滿足，重復(fù)循環(huán)體內(nèi)的執(zhí)行語句
        direction.forEach(([h, v]) => {
            const newX = x + h
            const newY = y + v
            if (arr[newX][newY] === 1 && !memo[newX][newY]) {
                memo[newX][newY] = true
                queue.push([newX, newY])
                result.push([newX, newY])
            }
        })
    }
    
    return result
}

fn([3, 4])

根據(jù)JavaScript的特性，可以對算法進(jìn)行優(yōu)化，對于上例的記憶數(shù)組，我們可以使用對象來處理，這樣可以減小初始化的開銷。代碼如下：

function fn([x, y]) {
    var memo = {}, // 將記憶數(shù)組改為記憶對象
        queue = [],
        result = [],
        direction = [[-1, 0],[1, 0],[0, -1],[0, 1]]

    if (arr[x][y] !== 1) {
        return false
    } else {
        queue.push([x, y])
        result.push(memo[x + "," + y] = [x, y])
    }

    while(queue.length > 0) {
        const [x, y] = queue.pop()
        direction.forEach(([h, v]) => {
            const newX = x + h
            const newY = y + v
            if (arr[newX][newY] === 1 && !memo[newX + "," + newY]) {
                queue.push([newX, newY]);
                result.push(memo[x + "," + y] = [newX, newY]);
            }
        })
    }
    return result;
}

當(dāng)然，對于遍歷如果我們使用遞歸方法的代碼的書寫量將會減少不少?？梢詫⒋a修改如下：

function fn(point) {
    var memo = {},
        result = [],
        direction = [[-1, 0],[1, 0],[0, -1],[0, 1]]
    function dg([x, y]) {
        result.push(memo[x + "," + y] = [x, y]);
        direction.forEach(([h, v]) => {
            const newX = x + h
            const newY = y + v
            if (arr[newX][newY] === 1 && !memo[newX + "," + newY]) {
                dg([newX, newY]);
            }
        })
    }
    dg(point);
    return result;
}

好了，今天寬度遍歷算法的就先說到這里，后續(xù)可能還會繼續(xù)修改，也歡迎各位批評指正。有問題或者有其他想法的可以在我的GitHub上pr。