Mój program działa dobrze, ale kiedy nie ma ścieżki przez labirynt, chcę wyjść "nie ma ścieżki". Ale teraz, jeśli nie ma ścieżki, nie mam nic z wyjścia. czy możesz mi z tym pomóc?

int A[4][4] = {
   1,1,0,1,
   1,0,1,0,
   1,0,1,0,
   0,0,1,1
};

int path[4][4] ={
  0,0,0,0,
  0,0,0,0,
  0,0,0,0,
  0,0,0,0
};
int findPath(int i, int j, int n){
  if (i == n-1 && j == n-1){
    path[i][j] = 1;
    return 1;
  }
  if (A[i][j] == 1) {
    path[i][j] = 1;
    if (findPath(i, j+1, n)==1) return 1;
    if (findPath(i+1, j, n)==1) return 1;
    path[i][j] = 0;
  }
  return 0;
}


int main() {
  int i,j;
  findPath(0,0,4);
  for (i = 0; i < 4; i++)
      for (j = 0; j < 4; j++)
          if (path[i][j])
              printf("(%d,%d)-->\n",i,j);
  printf("\n");
  return 0;
}
c
1
Triton 12 marzec 2020, 00:08

2 odpowiedzi

Najlepsza odpowiedź

Nie masz nic z wyjścia, ponieważ drukujesz tylko rzeczy, jeśli istnieje ścieżka. Tak więc twoje pytanie jest zasadniczo "Jak ustalić, czy nie ma ścieżki przez labirynt?"

Jedną z łatwej metody jest sprawdzenie przeciwieństwa tego stanu: jeśli w siatce ma miejsce, w którym można podróżować przez labirynt, a następnie istnieje ścieżka. Korzystanie z tego pomysłu prowadzi do następującej strategii: 1) Załóżmy, że ścieżka nie istnieje 2) Sprawdź, czy istnieje punkt, w którym istnieje ścieżka 3) sprawdź swoje założenie jeszcze raz na końcu. Prowadzi to do następującego kodu:

int no_path = 1; // 1) First assume there is no path.
                 // It may be preferable to include <stdbool.h> and
                 // use the provided boolean type.
for (i = 0; i < 4; i++) {
  for (j = 0; j < 4; j++) {
    if (path[i][j]) { // 2) Loop through and check if there is actually a path.
      printf("(%d,%d)-->\n",i,j);
      no_path = 0; // 2) Aha, there is a path after all!
    }
  }
}
if (no_path) { // 3) Check if no path exists once more at the end.
  printf("No path exists!\n");
}
2
Isaiah 11 marzec 2020, 21:33

W moim lokalnym czasie jest trochę za późno, aby pomyśleć, czy ten kod działa, więc założę się, że działa, jak zamierzasz. Potem myślę, że szukasz tego:

[...]
int main() {
  int i,j;
  if(findPath(0,0,4));
[...]
  else
    printf("There's no path");
  return 0;
}

Zdecydowanie radzę jednak czytać o wykresach.

0
jbulatek 11 marzec 2020, 22:33