inde alle möglichen Pfade durch ein Labyrin

Question

May 11, 2016, 03:55 AM

inde alle möglichen Pfade durch ein Labyrin

Ich versuche ein Programm zu erstellen, das ein zufällig generiertes Labyrinth durchläuft, in dem Einsen offen und Nullen Wände sind. von links oben bis rechts unten. Der Pfad kann nach oben, unten, links und rechts verlaufen.

erzeit gibt mir mein Programm eine Lösung, aber ich habe Probleme damit, mehr als einen Pfad zu drucke

Ich habe verschiedene Versionen dieses Problems gelesen, kann aber mit meinen Parametern keine finden.

Hier ist mein Code, ich habe den Teil weggelassen, in dem ich mein Labyrinth zufällig generiere.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

int  n, minMatrix, solIndex = 1, minLen = 10000000; //I use the latter 3 variables in order to find the shortest path, not relevant for now


bool solveMaze(int mat[n][n],int x, int y, int sol[][n], int count){

int i, j;
  if((!(x >= 0 && x <n  && y >=0 && y < n)) || mat[x][y] == 0 || sol[x][y] == 1){
    return false;
  }

  if(x == n-1 && y == n-1){
    sol[x][y] = 1;

    printf("Solution %d is:\n", solIndex);
    for(i = 0; i < n; i++)
    {
      for( j=0;j<n;j++)
      {
        printf("%d", sol[i][j]);
      }
      printf("\n");
    }

    if(count<minLen)
    {
      minLen = count;
      minMatrix = solIndex;
    }
    solIndex +=1;
    sol[x][y] = 0;
    return true;
  }

  sol[x][y] = 1;

  if(solveMaze(mat, x+1, y, sol, count+1)){
    return true;
  }

  if(solveMaze(mat, x-1, y, sol, count+1)){
    return true;
  }

  if(solveMaze(mat, x, y+1, sol, count+1)){
    return true;
  }

  if(solveMaze(mat, x, y-1, sol, count+1)){
    return true;
  }
  sol[x][y] = 0;
  return false;

}

Ich habe den Teil meines Mains weggelassen, in dem ich mein Labyrinth zufällig generiere.

int main(){

if(!solveMaze(**mat, 0, 0, sol, 0)){
    printf("No possible paths, run program again\n");
  }
  else{
    printf("the shortest path is %d\n", minMatrix);
  }
}

Zum Beispiel, wenn ich das Labyrinth haben

s gibt mir den ersten Pfad, den es find

Obwohl es einen Umweg braucht, um dorthin zu gelangen, ist es aufgrund der Vorlieben, in der Reihenfolge nach unten, oben, rechts und links zu fahren, immer noch ein Weg.

Letztendlich bin ich mir nicht sicher, wie ich mehrere Pfade durchlaufen soll.