algorithm - 需要图形问题的方法或解决方案

Question

给定一个字符串（“X”和“0”）的矩阵（维度= m X n），其中“X”代表对下棋完全不感兴趣的学生，“O”代表对国际象棋感兴趣的学生。找出班级中同时进行的国际象棋比赛的最大可能数量。我们必须使相邻的棋手成对。不考虑对角线对。

例如 1:3 3

噢噢噢

OXX

XXX 回答 = 2

例 2：4 5

哦哦哦

哦哦哦

OXXOO

OOOOO 答案 = 9

例如：3 2 3

XOX

噢噢噢

答案=1

标签： algorithm

Answer 1

正如评论的那样，我认为没有比暴力破解更好的方法了。我会从左上角到右下角迭代网格，并在每个空单元格中尝试三个选项之一（水平块、垂直块、留空），然后递归求解网格的其余部分。

如果网格的大小不是很大，您可以通过递归来解决这个问题。如果这导致堆栈溢出，则需要改用自定义堆栈。

function solve(grid, x = 0, y = 0) {
  // find first next empty cell
  while (y < grid.length && (x >= grid[y].length || grid[y][x] !== 'O')) {
    x++; // step to the right
    if (x >= grid[y].length) {
      // if we stepped out of the grid, go the next row
      x = 0;
      y++;
    }
  }

  // reached end of grid
  if (y >= grid.length) {
    return 0;
  }

  // three options:
  // - skip this cell
  // - put a horizontal block
  // - put a vertical block

  // skip this cell
  const results = [solve(grid, x + 1, y)];

  // put horizontal block
  if (x + 1 < grid[0].length && grid[y][x + 1] === 'O') {
    // step to (x+2, y) because (x+1, y) is already occupied
    results.push(solve(grid, x + 2, y) + 1);
  }

  // put vertical block
  if (y + 1 < grid.length && grid[y + 1][x] === 'O') {
    // mark (x, y+1) so we won't be able to use it once we reach that cell
    grid[y + 1][x] = '*'

    results.push(solve(grid, x + 1, y) + 1);

    // clear (x, y+1)
    grid[y + 1][x] = 'O'
  }

  return Math.max(...results);
}

console.log(solve([
  ['O', 'O', 'O'],
  ['O', 'X', 'X'],
  ['X', 'X', 'X']
]));
console.log(solve([
  ['O', 'O', 'O', 'O', 'O'],
  ['O', 'O', 'O', 'O', 'O'],
  ['O', 'X', 'X', 'O', 'O'],
  ['O', 'O', 'O', 'O', 'O']
]));
console.log(solve([
  ['X', 'O', 'X'],
  ['O', 'O', 'O']
]));