wuchaoliang1980
BAN USER{
#define RESULT_ROW 1024
#define N 5
bool back_tracking(int M[N][N],int x,int y,int **result,int *result_index){
////终止条件
if (x == N - 1 && y == N - 1 && M[x][y] == 0){
result[*result_index][0]= x;
result[*result_index][1] = y;
result_index++;
return true;
}
result[*result_index][0]= x;
result[*result_index][1] = y;
(*result_index)++;
if (x> N-1 || y> N-1) return false;
if (M[x][y] == 1){
return false;
}
if(back_tracking(M, x+1,y,result,result_index) == false){
(*result_index)--;
if (back_tracking(M, x,y+1,result,result_index) == false){
(*result_index)--;
return false;
}
}
return true;
}
bool find_one_path(int M[N][N],int x,int y){
int **result = (int **)malloc(sizeof(int*)*RESULT_ROW);
int result_count = 0;
for (int i = 0 ; i < RESULT_ROW;i++)
result[i]= (int *)malloc(sizeof(int)*2);
bool ret = back_tracking(M,0,0,result,&result_count);
if (ret){
printf("We find the path to the destination\n");
for(int i = 0 ;i < result_count -1 ;i++){
printf("(%d %d) ->",result[i][0],result[i][1]);
}
printf("(%d %d)",result[result_count -2][0],result[result_count -2][1]);
}
else
{
printf("We can not find the path to the destination\n");
}
for (int i = 0 ; i < RESULT_ROW;i++)
free(result[i]);
free(result);
}
void main(){
int M[N][N]={{0,0,0,1,0},{1,0,1,0,1},{1,0,0,0,0},{1,0,1,0,1},{0,0,1,0,0}};
return (find_one_path(M,0,0));
}
}
- wuchaoliang1980 September 24, 2021