[算法]棋盘攻击问题

liangbus commented 4 years ago

在象棋棋盘上，車是可以水平和垂直两个方向移动的，现给定一个 8x8 的棋盘，用一个二维数组表示，0代表该位置没有棋子，1代表该位置上的是車（该二维数组只有这两个值），当同一行或者同一列上，出现两个車，则认为该横盘上会产生相互攻击，现求，给定一个横盘，判定其是否出现相互攻击，若是则返回 true, 否则返回 false 示例：
```
[
[0,0,0,1, 0,0,0,0],
[0,0,0,0, 0,1,0,0],
[0,0,0,0, 0,0,0,0],
[0,0,0,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,0,0],
[0,0,0,0, 0,0,0,0]
]
```
说明：第一行第四列，与第四行每四列构成攻击状态，因此该棋盘返回状态为 true，其中第二行第六列的車没有与任何其他車构成攻击状态
在上一题的基础下，改为获取其中出现攻击可能的总次数示例：
```
[
[1,0,0,1, 0,0,0,1],
[0,0,0,0, 0,1,0,0],
[0,0,0,0, 0,0,0,0],
[0,0,0,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,0,0],
[0,0,0,1, 0,0,0,0]
]
```
说明：第一行第一列，跟第一行第四列和第一行第八列都构成攻击状态，图中出现攻击可能的总次数为 6 次

liangbus commented 4 years ago

暴力解第一问：

var board = [
  [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, 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, 1]
]
function isAttackedBoard(board) {
  const map = {}
  const len = board.length
  for(let i = 0; i < len; i++) {
    let row = board[i]
    for(let j = 0; j < row.length; j++) {
      const v = row[j]
      if(v) {
        if(map[`col-${j}`] || map[`row-${i}`]) return true
        map[`col-${j}`] = true
        map[`row-${i}`] = true
      }
    }
  }
  return false
}
console.log(isAttackedBoard(board)) // true

liangbus commented 4 years ago

暴力解第二问

在上面的基础上修改

var board = [
  [1, 0, 0, 1, 0, 0, 0, 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],
  [1, 0, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0, 1]
]
function isAttackedBoard(board) {
  const map = {}
  const len = board.length
  let count = 0
  for(let i = 0; i < len; i++) {
    let row = board[i]
    for(let j = 0; j < row.length; j++) {
      const v = row[j]
      if(v) {
        if(map[`col-${j}`]) count += map[`col-${j}`]
        if(map[`row-${i}`]) count += map[`row-${i}`]
        map[`col-${j}`] = map[`col-${j}`] ? ++map[`col-${j}`] : 1
        map[`row-${i}`] = map[`row-${i}`] ? ++map[`row-${i}`] : 1
      }
    }
  }
  return count
}
console.log(isAttackedBoard(board))

liangbus / blogging

[算法]棋盘攻击问题 #38

暴力解第一问：

暴力解第二问