迷路のようなバックトラック

Question

私は与えられた（X、Y）座標の開始点と終了点を持つ迷路ソルバを作ろうとしていますが、条件があります：新しい位置は以前の位置（a [x] [y] < = some_height_variabile）よりも低くなります。ここに私のコードは、これまでです：だから

#include <stdio.h> 

#define N 4 

int a[N][N] = 
{ 
    {35, 75, 80, 12}, 
    {13, 12, 11, 3}, 
    {32, 9, 10, 8}, 
    {12, 2, 85, 1} 
}; 

int sol[N][N]; 

int h, k, count; 
int end_x = -1, end_y = -1; 
int start_x = -1, start_y = -1; 

void print() 
{ 
    int i, j; 

    for (i = 0; i < N; i++) 
    { 
     for (j = 0; j < N; j++) 
     { 
      if (sol[i][j] > 0) 
       printf("%d ", sol[i][j]); 

      else 
       printf("_ "); 
     } 
     printf("\n"); 
    } 

    printf("\n"); 
} 

int solution(int x, int y) 
{ 
    return (x == end_x && y == end_y); 
} 

int valid(int x, int y) 
{ 
    return (x >= 0 && x < N && y >= 0 && y < N && a[x][y] <= h && !sol[x][y]); 
} 

void back(int x, int y) 
{ 
    if (valid(x, y)) 
    { 
     k ++; 
     sol[x][y] = k; 
     h = a[x][y]; // right here I'm updating the variabile 

     if (solution(x, y)) 
     { 
      count ++; 
      print(); 
     } 
     else 
     { 
      back(x + 1, y); 
      back(x, y + 1); 
      back(x - 1, y); 
      back(x, y - 1); 
     } 

     sol[x][y] = 0; 
     h = a[x][y]; // I actually don't know where to put this 
     k --; 
    } 
} 

int main(void) 
{ 
    int i, j; 

    for (i = 0; i < N; i++) 
    { 
     for (j = 0; j < N; j++) 
      printf("%d ", a[i][j]); 

     printf("\n"); 
    } 

    while (start_x >= N || start_x < 0 || start_y >= N || start_y < 0) 
    { 
     printf(">> Start X: "); scanf("%d", &start_x); 
     printf(">> Start Y: "); scanf("%d", &start_y); 
    } 

    h = a[start_x][start_y]; 

    while (end_x >= N || end_x < 0 || end_y >= N || end_y < 0) 
    { 
     printf(">> End X: "); scanf("%d", &end_x); 
     printf(">> End Y: "); scanf("%d", &end_y); 
    } 

    printf("Generated solutions:\n"); 
    back(start_x, start_y); 

    if (!count) 
     printf("No path was found!\n"); 

    return 0; 
} 

、start_x = 0、= 0 start_y、= 1 end_x、end_y = 3のために、それは持参してください35 - > 13 - > 12 - > 11 - > 3と35 - > 13 - > 12 - > 11 - > 10 - > 8 - > 3のソリューション

この状態がなければ、アルゴリズムはうまくいきます。h変数を更新する場所がわかりません。

Answer 1

あなたは正しい軌道にいると思います。しかし、変数hは冗長であるようです。代わりに、2つ以上のものが必要です。

1）前に特定のセルを訪れましたか？

2）前の移動の値。次のセルに移動するとき、または次のセルに移動するときに有効な移動があるかどうかを確認します。

#include <stdio.h> 

#define N 4 

int a[N][N] = 
{ 
    {35, 75, 80, 12}, 
    {13, 12, 11, 3}, 
    {32, 9, 10, 8}, 
    {12, 2, 85, 1} 
}; 

int sol[N][N]; 
int visited[N][N]; 

int h, k, count; 
int end_x = -1, end_y = -1; 
int start_x = -1, start_y = -1; 

void print() 
{ 
    int i, j; 

    for (i = 0; i < N; i++) 
    { 
     for (j = 0; j < N; j++) 
     { 
      if (sol[i][j] > 0) 
       printf("%d ", sol[i][j]); 

      else 
       printf("_ "); 
     } 
     printf("\n"); 
    } 

    printf("\n"); 
} 

int solution(int x, int y) 
{ 
    return (x == end_x && y == end_y); 
} 

int valid(int x, int y, int currentCellValue) 
{ 
    return (x >= 0 && x < N && y >= 0 && y < N && a[x][y] <= currentCellValue && !sol[x][y] && !visited[x][y]); 
} 

void back(int x, int y, int curr) 
{ 
    if (valid(x, y, curr)) 
    { 
     k ++; 
     sol[x][y] = k; 
     visited[x][y] = 1; 

     if (solution(x, y)) 
     { 
      count ++; 
      print(); 
     } 
     else 
     { 
      back(x + 1, y, a[x][y]); 
      back(x, y + 1, a[x][y]); 
      back(x - 1, y, a[x][y]); 
      back(x, y - 1, a[x][y]); 
     } 

     sol[x][y] = 0; 
     visited[x][y] = 0; 
     k --; 
    } 
} 

int main(void) 
{ 
    int i, j; 

    for (i = 0; i < N; i++) 
    { 
     for (j = 0; j < N; j++) 
      printf("%d ", a[i][j]); 

     printf("\n"); 
    } 

    while (start_x >= N || start_x < 0 || start_y >= N || start_y < 0) 
    { 
     printf(">> Start X: "); scanf("%d", &start_x); 
     printf(">> Start Y: "); scanf("%d", &start_y); 
    } 

    h = a[start_x][start_y]; 

    while (end_x >= N || end_x < 0 || end_y >= N || end_y < 0) 
    { 
     printf(">> End X: "); scanf("%d", &end_x); 
     printf(">> End Y: "); scanf("%d", &end_y); 
    } 

    printf("Generated solutions:\n"); 
    back(start_x, start_y, a[start_x][start_y]); 

    if (!count) 
     printf("No path was found!\n"); 

    return 0; 
} 

動きが有効であるかどうかを確認するためにisValid関数に渡され、現在のセルの値を渡す方法back通知に通話中に次のように

あなたの修正コードがありますない。

int visited[N][N];同じセルを何度も繰り返し訪問することはありません。