需求

假设有一块区域（例如 50 * 50），区域被划分成无数的正方形地块，地块有三种状态，分别是：平原、沼泽、山地。现在要在整个区域内选出一个给定边长的正方形区域，要求如下：

• 目标区域内不可以有山地地块。
• 目标区域要尽可能少的包含沼泽地块。

需要完成一个函数，参数为地形数据 map（一个二维数字数组，元素的值分别为：0 平原、1 沼泽、2 山地）和目标正方形区域的边长 targetLength，返回最适合建造的区域的中心点坐标（若目标区域边长为偶数则可返回小数坐标）。

思路

建模

接下来我们分析一下题目，完整的算法在本文最下面。由于需求分为 寻找不包含地块的区域（有效正方形） 和 尽可能少的包含沼泽，所以我们可以建立两个模型：

• dp[i][j].len 代表以坐标 [i][j]（i 为纵坐标，j 为横坐标，下同）为右下角时所能生成的最大正方形的边长。
• dp[i][j].swamp 代表以坐标 [i][j] 为右下角，[0][0] 为左上角的矩形区域内的沼泽数量之和（伪前缀和）。

首先我们通过 dp[i][j].len 得出该点代表的正方形是否符合给定的正方形区域边长，如果符合的话再通过 dp[i][j].swamp 求出区域内的沼泽数量，并与当前的最小沼泽数量比较，如果更小的话那自己即为新的结果。

状态转移

首先我们先来找 dp[i][j].len 的状态转移方程，由于求有效正方形只跟山地和平原有关，所以我们先忽略掉沼泽，如下图，每个地块中的数字即为对应的 dp[i][j].len：

因为我们规定 dp[i][j].len 就是以该点坐标为正方形的 右下角 时所能生成最大正方形的边长。所以可以发现该点的值是和其上方、左上、左侧三个节点的值相关的：

并且由于大家都是正方形，所以本节点的正方形大小取决于这三个中 边长最小 的节点。例如上图，左侧的节点是山地，所以其代表的正方形边长为 0（其作为右下角不能生成正方形 ）。那么黄色节点所能生成的最大正方形边长就是 0 + 1 = 1（他自己为一个独立的正方形 ）。由此，我们就可以得到其状态转移方程：

dp[i][j].len = Math.min(dp[i - 1][j - 1].len, dp[i][j - 1].len dp[i - 1][j].len) + 1 

接下来我们来看一下 dp[i][j].swamp 怎么推导，想要算当前到左上角的所有沼泽数量，依旧是需要左侧、上方、左上三块区域内的沼泽数量。如下图，若要求红色区域内的沼泽数量，那么就是 蓝色区域沼泽数量 + 紫色区域沼泽数量 - 黄色区域沼泽数量 + 自己是否为沼泽（因为黄色区域被重复计算了一次，所以需要减去 ）。

所以，dp[i][j].swamp 的状态转移方程如下：

dp[i][j].swamp =  dp[i - 1][j].swamp + dp[i][j - 1].swamp - dp[i - 1][j - 1].swamp + (map[i][j] === 1 ? 1 : 0)

通过这种方式，我们也就可以逆推出指定边长正方形中的沼泽数量，如下：。

红色区域内的沼泽数量就等同于 dp[i][j].swamp - 蓝色区域沼泽数量 - 紫色区域沼泽数量 + 黄色区域沼泽数量，即：

// currentSwamp 代表以 [i][j] 为右下角 以 dp[i][j].len 为边长的正方形中的沼泽数量
currentSwamp = dp[i][j].swamp -  dp[i - 1][j].swamp -  dp[i][j - 1].swamp +  dp[i - 1][j - 1].swamp

通过上面三个方程我们可以看出，左上、上、左三个节点的值扮演了非常重要的角色，所以我们可以对其进行抽象，我们把 dp[i][j].len 和 dp[i][j].swamp 方程中的三个节点看作是获取右下角边长为 1 的正方形相邻的三个节点，就可以通过把 右下角正方形边长 提取成参数的形式，来统一三个方程中相邻节点的获取过程：

翻译成代码并添加越界检查之后就是如下函数：

/**
 * 获取状态转移所需的三个相邻节点
 * 
 * @param {object[][]} dp 状态集
 * @param {number} i 目标正方形右下角的 y 坐标
 * @param {number} j 目标正方形右下角的 x 坐标
 * @param {number} len 右下角正方形的边长
 */
function getOtherArea(dp, i, j, len) {
    // 越界时的默认值
    const nullNode = { len: 0, swamp: 0 }
    // 检查索引是否小于零，小于零就返回默认值
    return {
        topLeft: (i - len > -1 && j - len > -1) ? dp[i - len][j - len] : nullNode,
        top: (i - len > -1) ? dp[i - len][j] : nullNode,
        left: (j - len > -1) ? dp[i][j - len] : nullNode,
    }
}

之后，我们按照刚开始提到的流程，把这三部分代码按顺序装在一起，然后添加个通过右下角和边长获取正方形中心坐标的辅助函数，就可以完成如下的最终解法了.

完整算法

/**
 * 寻找可行的最佳选址
 * 
 * @param {number[][]} map 二维数组，代表了地图信息，元素为数字，对应关系为：0 平原、1 沼泽、2 山地
 * @param {number} targetLength 建筑区域的边长
 * @returns {[number, number][]} 二位数组，包含了所有最佳选址的中央点的 xy 坐标
 */
function getBasePos(map, targetLength) {
    let dp = Array(map.length).fill().map(_ => [])
    // 合适的结果集
    let result = []
    // 结果集里对应的沼泽数量
    let minSwamp = Infinity

    // 遍历所有地块
    for (let i = 0; i < map.length; i ++) {
        for (let j = 0; j < map[i].length; j ++) {
            const { topLeft, top, left } = getOtherArea(dp, i, j, 1)

            // 生成当前位置的状态
            dp[i][j] = {
                // 以当前位置为右下角，可以生成的最大正方形的边长
                len: map[i][j] === 2 ? 0 : (Math.min(topLeft.len, top.len, left.len) + 1),
                // 以当前位置为右下角，[0][0] 为左上角的区域内所有的沼泽数量
                swamp: top.swamp + left.swamp - topLeft.swamp + (map[i][j] === 1 ? 1 : 0)
            }

            // 发现该正方形已经可以满足要求了
            if (dp[i][j].len >= targetLength) {
                // 获取正方形右上侧的三个区域
                const { topLeft, top, left } = getOtherArea(dp, i, j, targetLength)
                // 计算出当前区域内的沼泽数量
                const currentSwamp = dp[i][j].swamp - top.swamp - left.swamp + topLeft.swamp

                // 对比沼泽数量并更新结果
                if (currentSwamp < minSwamp) {
                    minSwamp = currentSwamp
                    result = [ getCenterBybottomRight(i, j, targetLength) ]
                }
                else if (currentSwamp === minSwamp) result.push(getCenterBybottomRight(i, j, targetLength))
            }
        }
    }

    return result
}

/**
 * 获取状态转移所需的三个相邻节点
 * 
 * @param {object[][]} dp 状态集
 * @param {number} i 目标正方形右下角的 y 坐标
 * @param {number} j 目标正方形右下角的 x 坐标
 * @param {number} len 正方形的边长
 */
function getOtherArea(dp, i, j, len) {
    // 越界时的默认值
    const nullNode = { len: 0, swamp: 0 }
    // 检查索引是否小于零，小于零就返回默认值
    return {
        topLeft: (i - len > -1 && j - len > -1) ? dp[i - len][j - len] : nullNode,
        top: (i - len > -1) ? dp[i - len][j] : nullNode,
        left: (j - len > -1) ? dp[i][j - len] : nullNode,
    }
}

/**
 * 获取该正方形中心点的坐标
 * 
 * @param {number} i 正方形右下角的 y 坐标
 * @param {number} j  正方形右下角的 x 坐标
 * @param {number} len 正方形的边长
 * @returns {[ number, number ]} [0] 为中央点 x 坐标，[1] 为 y 坐标
 */
function getCenterBybottomRight(i, j, len) {
    return [
        i - (len / 2) + 0.5,
        j - (len / 2) + 0.5,
    ]
}

随机测试用例

// 随机地图的宽
const MAP_WIDTH = 20
// 随机地图的长
const MAP_HEIGHT = 25
// 目标建筑的边长
const BASE_LENGTH = 3

// 生成随机地图
const getRandMap = function(width, height) {
    // 提高 roll 中平原的概率，不然太难形成大片空地了
    const randSet = [ 0, 0, 0, 1, 2 ]
    return Array(height).fill().map(_ => Array(width).fill().map(_ => {
        return randSet[Math.floor(Math.random() * randSet.length)]
    }))
}

// 生成地图并进行查找
const randMap = getRandMap(MAP_WIDTH, MAP_HEIGHT)
const result = getBasePos(randMap, BASE_LENGTH)

// 绘制地图，▢ 平原、▤ 沼泽、▣ 山地
console.log(randMap[0].map((_, i) => i < 10 ? `${i}  ` : `${i} `).join(''))
console.log(randMap.map((line, index) => line.map(val => [ '▢', '▤', '▣' ][val]).join('  ') + `  ${index}`).join('\n'))
// 打印结果
console.log("\nresult：", result.map(pos => `${pos[0]},${pos[1]}`).join('   '))

测试结果：