function getWeiQiAir(str) {
    let [black, white] = str.split('\n')
    black = black.split(' ').map(Number)
    white = white.split(' ').map(Number)
    // value: 0 ,1,2表示空、黑、白,white和black属性用于表示是否已经计算过黑白棋的气。
    // 注意生成的二维数组不能直接用fill填{ value: 0, white: true, black: true }。这样会导致引用一致，改一个value，所有的value都会变。
    let qipan = new Array(19).fill(0).map(v => new Array(19).fill(0).map(v => ({ value: 0, white: true, black: true })))
    // 棋盘上下对应的棋
    let lenB = black.length
    for (let i = 0; i < lenB; i = i + 2) {
        qipan[black[i]][black[i + 1]].value = 1
    }
    let lenW = white.length
    for (let i = 0; i < lenW; i = i + 2) {
        qipan[white[i]][white[i + 1]].value = 2
    }
    let sum = 0
    // 计算黑棋的气
    for (let i = 0; i < lenB; i = i + 2) {
        let x = black[i]
        let y = black[i + 1]
        // 第一个条件判断某一个方向是否为空，第二个条件判断是否被当前颜色计算过
        // 注意如果棋下在边界需要考虑数组越界问题。这里使用?.访问，当属性不存在时会返回undefined
        if (qipan?.[x - 1]?.[y]?.value == 0 && qipan[x - 1][y].black) {
            qipan[x - 1][y].black = false
            sum++
        }
        if (qipan[x]?.[y - 1]?.value == 0 && qipan[x][y - 1].black) {
            qipan[x][y - 1].black = false
            sum++
        }
        if (qipan?.[x + 1]?.[y]?.value == 0 && qipan[x + 1][y].black) {
            qipan[x + 1][y].black = false
            sum++
        }
        if (qipan[x]?.[y + 1]?.value == 0 && qipan[x][y + 1].black) {
            qipan[x][y + 1].black = false
            sum++
        }
    }
    // 计算白棋的气
    for (let i = 0; i < lenW; i = i + 2) {
        let x = white[i]
        let y = white[i + 1]
        if (qipan?.[x - 1]?.[y]?.value == 0 && qipan[x - 1][y].white) {
            qipan[x - 1][y].white = false
            sum++
        }
        if (qipan[x]?.[y - 1]?.value == 0 && qipan[x][y - 1].white) {
            qipan[x][y - 1].white = false
            sum++
        }
        if (qipan?.[x + 1]?.[y]?.value == 0 && qipan[x + 1][y].white) {
            qipan[x + 1][y].white = false
            sum++
        }
        if (qipan[x]?.[y + 1]?.value == 0 && qipan[x][y + 1].white) {
            qipan[x][y + 1].white = false
            sum++
        }
    }
    return sum
}
console.log(getWeiQiAir(`0 5 8 9 9 10
5 0 9 9 9 8`))

用连续自然数之和来表达整数

考察数学，双指针

题目描述

一个整数可以由连续的自然数之和来表示。

给定一个整数，计算该整数有几种连续自然数之和的表达式，且打印出每种表达式

输入描述

一个目标整数T (1 <=T<= 1000)

输出描述

该整数的所有表达式和表达式的个数。如果有多种表达式，输出要求为：

自然数个数最少的表达式优先输出

每个表达式中按自然数递增的顺序输出，具体的格式参见样例。

在每个测试数据结束时，输出一行”Result:X”，其中X是最终的表达式个数。

示例1

输入

输出

9=9

9=4+5

9=2+3+4

Result:3

说明

整数9有三种表达方法

示例2

输入

输出

10=10

10=1+2+3+4

Result:2

解析

方法一：通过遍历加计算，假设有i个数合为目标数n，其中最小的数为m，即m，m+1,m+2,...,m+i-1的和为n，即i*m+1+2+...+i-1=n。故n减去1加到i-1的和

需要被m整除即可。

方法二：类似于双指针，用i和j指向头和尾(i<j)，i一直加到j如果大于等于目标值时（等于的时候还需要记录结果），i加一，如果小于目标值时j+1，

当i和j都大于目标值除以2时结束循环。

答案

// 方法一
function continusInteger(n) {
    let res = [`${n}=${n}`]
    for (let i = 2; i < Math.floor(n / 2); i++) {
        // new Array(i).fill(0).reduce((t,v,i)=>t+i)表示1+2+...+i-1
        let tmp = n - new Array(i).fill(0).reduce((t, v, i) => t + i)
        let start = tmp / i
        // 找到最小的数start，拼接连续自然数加入结果数组中
        if (Number.isInteger(start)) {
            let str = `${n}=${start}`
            for (j = 1; j < i; j++) {
                str = str + `+${start + j}`
            }
            res.push(str)
        }
    }
    return `${res.join('\n')}\nResult:${res.length}`
}
// 方法二
function continusInteger(n) {
    if (n < 3) {
        return `${n}=${n}\nRestult:1`
    }
    let res = [`${n}=${n}`]
    let i = 1, j = 2
    sum = i + j
    while (i < n / 2 || j < n / 2) {
        if (sum < n) {
            j++
            sum = sum + j
        } else if (sum > n) {
            sum = sum - i
            i++
        } else {
            // 找到目标值记录
            let str = `${n}=${i}`
            for (let x = i + 1; x <= j; x++) {
                str = str + `+${x}`
            }
            res.push(str)
            j++
            sum = sum + j
        }
    }
    return `${res.join('\n')}\nResult:${res.length}`
}
console.log(continusInteger(9))
console.log(continusInteger(10))

亲子游戏

考察深度遍历、递归

题目描述

宝宝和妈妈参加亲子游戏，在一个二维矩阵（N*N）的格子地图上，宝宝和妈妈抽签决定各自的位置，地图上每个格子有不同的糖果数量，部分格子有障碍物。

游戏规则是妈妈必须在最短的时间（每个单位时间只能走一步）到达宝宝的位置，路上的所有糖果都可以拿走，不能走障碍物的格子，只能上下左右走。

请问妈妈在最短到达宝宝位置的时间内最多拿到多少糖果（优先考虑最短时间到达的情况下尽可能多拿糖果）。

输入描述

第一行输入为N，N标识二维矩阵的大小

之后N行，每行有N个值，表格矩阵每个位置的值

其中：

-3：妈妈

-2：宝宝

-1：障碍

=0：糖果数(0表示没有糖果，但是可以走)

输出描述

输出妈妈在最短到达宝宝位置的时间内最多拿到多少糖果，行末无多余空格

示例1

输入输出示例仅供调试，后台判题数据一般不包含示例

输入

3 2 1 -3

1 -1 1 1

1 1 -1 2

-2 1 2 3

输出

说明

此地图有两条最短路径可到宝宝位置，绿色线和黄色线都是最短路径6步，但是黄色拿到的糖果更多，9个

示例2

输入

3 2 1 -3

-1 -1 1 1

1 1 -1 2

-2 1 -1 3

输出

-1

说明

此地图妈妈无法到达宝宝位置

备注

地图最大5050

解析

1.用二维数组表示图中每个点，每个点为一个对象v属性对应每个点的数值，can属性对应是否可以经过。

2.用深度遍历来找出结果：

1.首先f(start,end)表示从起点到终点获得的最短路劲已经最大糖果数。f(start,end)等于min(f(start-top,end),f(start-bottom,end),f(start-left,end),f(start-end,end))。其中start-top表示start位置向

上走一格后的位置。这里表示从4个方向走一格后到终点位置的值，取最短的一个路径,注意如果路径同样短的要取一个糖果多的，所以f(start,end)需要

返回2个结果一个为最短路径和最大的糖果数。

2.找终点：

1>当start和end对应的横、纵坐标之差的绝对值为1时，说明起点和终点相邻，即可以直接退出。

2>当当前的步数已经大于等于已有成功的步数时，可以直接退出。

3>每次走过的位置，把can属性设置为false，防止走回头路，当4个方向都走不了时，直接退出。

4>每次走完后需要还原之前的步数、糖果数、起点坐标以及数组中的是否已经经过的属性can。

function getMinPath(str) {
    let arr = str.split('\n')
    let len = Number(arr.shift())
    let start = {}, end = {}
    // 用二维数组表示图中的每个点
    arr = arr.map((v, i) => v.split(' ').map((v, j) => {
        v = Number(v)
        // 记录起点和终点的位置
        if (v === -3) {
            start.x = i
            start.y = j
        }
        if (v === -2) {
            end.x = i
            end.y = j
        }
        return { v, can: true }
    }))
    let res = bfs(start, end, 0, 0, len, arr)
    if (res) {
        return res[1]
    }
    return -1
}
function bfs(start, end, step, candi, len, arr, min = Infinity, max = 0) {
    if (Math.abs(start.x - end.x) + Math.abs(start.y - end.y) === 1) {
        return [step, candi]
    }
    if (step >= min) {
        return
    }
    if (start.x + 1 < len) {
        if (arr[start.x + 1][start.y].v >= 0 && arr[start.x + 1][start.y].can) {
            start.x++
            step++
            candi += arr[start.x][start.y].v
            arr[start.x][start.y].can = false
            let r = bfs(start, end, step, candi, len, arr, min, max)
            if (r) {
                if (r[0] < min) {
                    // 当前解的步数小于已有的成功步数，
                    min = r[0]
                    max = r[1]
                } else if (r[0] === min && r[1] > max) {
                    // 当前解的步数等于已有的成功步数，糖果数大于已有成功步数的糖果数
                    判断当前解的
                    max = r[1]
                }
            }
            //还原
            start.x--
            step--
            candi -= arr[start.x][start.y].v
            arr[start.x][start.y].can = true
        }
    }
    if (start.x - 1 >= 0) {
        if (arr[start.x - 1][start.y].v >= 0 && arr[start.x - 1][start.y].can) {
            start.x--
            step++
            candi += arr[start.x][start.y].v
            arr[start.x][start.y].can = false
            let l = bfs(start, end, step, candi, len, arr, min, max)
            if (l) {
                if (l[0] < min) {
                    min = l[0]
                    max = l[1]
                } else if (l[0] === min && l[1] > max) {
                    max = l[1]
                }
            }
            //还原
            start.x++
            step--
            candi -= arr[start.x][start.y].v
            arr[start.x][start.y].can = true
        }
    }
    if (start.y + 1 < len) {
        if (arr[start.x][start.y + 1].v >= 0 && arr[start.x][start.y + 1].can) {
            start.y++
            step++
            candi += arr[start.x][start.y].v
            arr[start.x][start.y].can = false
            let t = bfs(start, end, step, candi, len, arr, min, max)
            if (t) {
                if (t[0] < min) {
                    min = t[0]
                    max = t[1]
                } else if (t[0] === min && t[1] > max) {
                    max = t[1]
                }
            }
            //还原
            start.y--
            step--
            candi -= arr[start.x][start.y].v
            arr[start.x][start.y].can = true
        }
    }
    if (start.y - 1 >= 0) {
        if (arr[start.x][start.y - 1].v >= 0 && arr[start.x][start.y - 1].can) {
            start.y--
            step++
            candi += arr[start.x][start.y].v
            arr[start.x][start.y].can = false
            let b = bfs(start, end, step, candi, len, arr, min, max)
            if (b) {
                if (b[0] < min) {
                    min = b[0]
                    max = b[1]
                } else if (b[0] === min && b[1] > max) {
                    max = b[1]
                }
            }
            //还原
            start.y++
            step--
            candi -= arr[start.x][start.y].v
            arr[start.x][start.y].can = true
        }
    }
    if (min !== Infinity) {
        return [min, max]
    }
}
console.log(getMinPath(`4
3 2 1 -3
1 -1 1 1
1 1 -1 2
-2 1 2 3`))
console.log(getMinPath(`4
3 2 1 -3
-1 -1 1 1
1 1 -1 2
-2 1 -1 3`))

本作品采用知识共享署名 4.0 国际许可协议进行许可