题解 | #走方格的方案数#

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});
rl.on('line', function (line) {
    const [m, n] = line.split(' ').map(it => +it);
    let res = []
    bfs(m, n, res, [['0,0']]);
    console.log(res.length);
});

function bfsTraceS(m: number, n: number, res: string[][], traces: string[][]){
  let arr: string[][] = []
  for (const trace of traces) {
    let [x,y] = trace[trace.length - 1].split(',').map(it=>+it);
    if(x === m && y === n){
      res.push(trace)
    }
    if (x < m){
      let temp = Array.from(trace)
      temp.push(`${x + 1},${y}`)
      arr.push(temp)
    }
    if(y < n){
      let temp = Array.from(trace)
      temp.push(`${x},${y + 1}`)
      arr.push(temp)
    }
  }
  if(arr.length){
    bfsTraceS(m, n, res, arr)
  }
}

其实我在看到题目的时候第一个想到的是回溯+搜索，其实只需要广度优先搜索就可以了。这种做法能够得到最终结果，但是我看了一下其他题解，有递归、动态规划，也有根据排列组合直接计算的，都比本解法要简单。本解法的唯一优点是能得到每种走法的路径。