算法：动态规划 寻找2D矩阵中到达某一坐标的可能路径总数进阶版（添加路障）
dp基础问题： 寻找2D矩阵中到达某一坐标的可能路径总数（含路障）
问题描述：
问题和上一篇博文类似，不过这次加上一个设定：有一些坐标为路障，不让通行。
分析：
加上路障之后，大致的解题思路是一样的，但是有一些条件需要被考虑到我们求解的过程中：
- 如果起始坐标就是路障，则问题无解
- 如果在行进过程中遇到路障，则 numWays[i][j] 的值设为一个不存在的值，因为坐标(i,j)无法到达。
- 如果最顶或者最左的坐标遇到一个路障，则路障之后的所有坐标都无法到达。
考虑到这些条件，此问题的算法如下：
算法：
/**
*
* @param {int} x
* @param {int} y
*/
var twodimensional = function(x, y) {
// construc numWays dp 2-dimensional-matrix
var numWays = new Array()
for (let i = 0; i < y; i++) {
a[i] = new Array()
for (let j = 0; j < x; j++) {
a[i][j] = 0
}
}
// set 5 blocked position
for(let i = 0; i < 5; i++) {
a[Math.floor((Math.random()*x)+1)][Math.floor((Math.random()*x)+1)] = -1;
}
// no way
if (a[0][0] = -1) {
console.log('0')
return 0
}
// construct topmost ways
for (let i = 1; i < x; i++) {
if (a[0][i] === 0) {
numWays[0][i] = 1
} else {
break;
}
}
// construct leftmost ways
for (let i = 1; i < y; i++) {
if (a[i][0] === 0) {
numWays[i][0] = 1
} else {
break
}
}
// find all ways
for (let i = 1; i < x; i++) {
for (let j = 1; j < y; j++ ) {
if (a[i][j] === -1) continue
if (a[i - 1][j] != -1) {
numWays[i][j] = numWays[i - 1][j] + numWays[i][j]
}
if (a[i][j - 1] != -1) {
numWays[i][j] = numWays[i][j - 1] + numWays[i][j]
}
}
}
return numWays[x - 1][y - 1] >= 0 ? numWays[x - 1][y - 1] : 0
}