连连看

连连看是一款经典的消除类益智游戏,你需要实现一个算法来判断两个方块是否可以连接并消除。

游戏规则

  • 当且仅当两个方块的值相同时,它们才可能被连接
  • 连接线必须由不超过三条线段组成(即最多有两个转折点)
  • 连接线除了经过选中的两个方块外,不能经过任何其他非空方块
  • 连接线允许"出界"(即可以在棋盘外折弯再回到棋盘内)

输入输出

  • board: 游戏板二维数组,0表示空格,非0数字表示方块类型
  • row1, col1: 第一个选中方块的坐标
  • row2, col2: 第二个选中方块的坐标
  • 返回值:如果可以连接则返回连接路径坐标数组,否则返回空数组

示例

输入:
board = [
  [1, 2, 3],
  [0, 0, 3],
  [1, 0, 0]
]
row1 = 0, col1 = 0, row2 = 2, col2 = 0

输出: [[0,0], [1,0], [2,0]]
解释: 两个值为1的方块可以通过一条直线连接,返回路径坐标
输入:
board = [
  [1, 2, 1],
  [3, 0, 3],
  [0, 0, 0]
]
row1 = 0, col1 = 0, row2 = 0, col2 = 2

输出: []
解释: 两个值为1的方块之间有一个值为2的方块阻隔,无法连接,返回空数组

祝你好运!