你如何解决这个问题::
机器人位于 4x4 网格的左上角。机器人可以上下左右移动,但不能两次访问同一地点。机器人正试图到达网格的右下角。
我的想法:
回溯解决方案,我们遍历所有解决方案的树并在到达目标单元格后打印。我实现了这一点,但我不确定它是否正确或有意义,或者它是否是正确的方法。我已经在这里发布了代码,如果有人能解释它有什么问题,我将不胜感激。
递归解决方案,我从起始单元格开始,递归地从每个相邻单元格找到目标单元格的路径,基本情况是到达目标单元格。
问题:
1)这两种表达方式是否相同?
2)这些想法是否有意义?
3)这些解决方案的时间复杂度是多少?我认为第二个是 4^n?
4)我的回溯代码有意义吗?
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;
}