通过4x4网格查找所有路径

Question

我的想法：

回溯解决方案，我们通过所有解决方案的树和打印，一旦我们达到目标单元格。我实现了这一点，但我不确定它是否正确或有意义，或者它是否是正确的方法。我在这里发布了代码，如果有人能解释它的错误，我将非常感谢。

递归解决方案，我从起始单元格开始，并从每个相邻单元格递归地找到目标单元格的路径，基本情况是击中目标单元格。

5）有没有更简单的方法来做到这一点？

下面是我的代码，它打印N=4的正确路径数。正确吗？

#define N 4
int counter = 0;
bool legal_move(int x, int y, int array[N+2][N+2]){
  bool ret = (array[x][y] == 1);
  array[x][y] = 0;
  return ret;
}

/*
void print_array(int array[N+2][N+2]){
  for(int i = 0; i < N+2; i++){
    for(int j = 0; j < N+2; j++)
      cout << array[i][j] << " ";
    cout << endl;
  }
  cout << endl << endl;
}
*/

void print_paths(int x, int y, int n, int m, int array[N+2][N+2]){
  if(x == n && y == m){
    print_array(array);
    counter++;
  }
  else {
    int dx = 1;
    int dy = 0;
    for(int i = 0; i < 4; i++){
      if(legal_move(x + dx, y + dy, array)){
        print_paths(x + dx, y + dy, n, m, array);
        array[x+dx][y+dy] = 1;
      }
      swap(dx,dy);
      if(i == 1)
        dx = -dx;
    }
  }
}

int main(){

  int array[N+2][N+2];

  for(int i = 1; i < N+1; i++)
    for(int j = 1; j < N+1; j++)
      array[i][j] = 1;

  for(int i = 0; i < N+2; i++)
    array[0][i] = array[i][0] = array[N+1][i] = array[i][N+1] = 0;

//print_array(array);
  array[1][1] = 0;  //Set start cell to be seen.
  print_paths(1,1,N,N,array);
  cout << counter << endl;
}

Answer 1

我想是同样的想法。

您的代码的问题是您没有实现“但不能正确地访问同一地点两次”。

假设你的机器人从S走到A的某个路径，你现在正在检查是否去A附近的B，测试应该是“机器人以前在当前路径上去过B吗”。但是你所实现的是‘机器人以前是否在任何路径上访问过B’。