So finden Sie die schnellste Route in einem Labyrinth (in C) [duplizieren]
Diese Frage hat hier bereits eine Antwort:
Programmiertheorie: Löse ein Labyrinth 14 answersDas Labyrinth ist als quadratische Matrix definiert. Beispielsweise
int maze[N][N] =
{ { 1, 1, 1, 1, 1, 1, 1 },
{ 0, 1, 0, 1, 0, 0, 1 },
{ 0, 1, 0, 1, 1, 1, 1 },
{ 0, 1, 0, 0, 0, 1, 1 },
{ 0, 1, 1, 1, 0, 1, 1 },
{ 0, 0, 1, 0, 1, 1, 1 },
{ 1, 1, 1, 1, 0, 1, 1 } };
Sie können nur dort gehen, wo es eine 1 gibt. Sie können einen Schritt nach unten, oben, links und rechts machen. Sie beginnen in der oberen linken Ecke und enden in der unteren rechten Ecke.
Die Ausgabe sollte die Mindestanzahl von Schritten sein, um ein Labyrinth fertigzustellen. Wir können davon ausgehen, dass es mindestens einen Weg gibt, um das Labyrinth zu beenden. Ich habe den Code überarbeitet und dachte, ich hätte alles abgedeckt. Aber offensichtlich fehlt mir etwas. danke für Ihre Hilf
int path_help(int maze[][N], int row, int col, int count)
{
int copy1[N][N], copy2[N][N], copy3[N][N];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
copy1[i][j] = maze[i][j];
copy2[i][j] = maze[i][j];
copy3[i][j] = maze[i][j];
}
}
int a, b, c, d;
if (col == 0 || row == 0)
{
if (row == N - 1)
{
if (maze[row][col + 1] == 1)
{
maze[row][col] = 0;
return path_help(maze, row, col + 1, count + 1);
}
else return N*N;
}
if (col == N - 1)
{
if (maze[row + 1][col] == 1)
{
maze[row][col] = 0;
return path_help(maze, row + 1, col, count + 1);
}
else return N*N;
}
if (maze[row][col + 1] == 1 && maze[row + 1][col] == 1)
{
maze[row][col] = 0;
copy1[row][col] = 0;
return min(path_help(copy1, row, col + 1, count + 1),path_help(maze, row + 1, col, count + 1));
}
if (maze[row][col + 1] == 0 && maze[row + 1][col] == 1)
{
maze[row][col] = 0;
return path_help(maze, row + 1, col, count + 1);
}
if (maze[row + 1][col] == 0 && maze[row][col + 1] == 1)
{
maze[row][col] = 0;
return path_help(maze, row, col + 1, count + 1);
}
else return N*N;
}
if (col == N - 1 || row == N - 1)
{
if (col == N - 1 && row == N - 1) return count;
if (row == N - 1)
{
if (maze[row - 1][col] == 1 && maze[row][col + 1] == 1)
{
maze[row][col] = 0;
copy1[row][col] = 0;
return min(path_help(copy1, row, col + 1, count + 1), path_help(maze, row - 1, col, count + 1));
}
if (maze[row - 1][col] == 0 && maze[row][col + 1] == 1)
{
maze[row][col] = 0;
return path_help(maze, row, col + 1, count + 1);
}
if (maze[row][col + 1] == 0 && maze[row - 1][col] == 1)
{
maze[row][col] = 0;
return path_help(maze, row - 1, col, count + 1);
}
else return N*N;
}
if (col == N - 1)
{
if (maze[row + 1][col] == 1 && maze[row][col - 1] == 1)
{
maze[row][col] = 0;
copy1[row][col] = 0;
return min(path_help(copy1, row, col - 1, count + 1), path_help(maze, row + 1, col, count + 1));
}
if (maze[row + 1][col] == 0 && maze[row][col - 1] == 1)
{
maze[row][col] = 0;
return path_help(maze, row, col - 1, count + 1);
}
if (maze[row][col - 1] == 0 && maze[row + 1][col] == 1)
{
maze[row][col] = 0;
return path_help(maze, row + 1, col, count + 1);
}
else return N*N;
}
}
if (maze[row + 1][col] == 1)
{
maze[row][col] = 0;
a = path_help(maze, row + 1, col, count + 1);
}
else a = N*N;
if (maze[row - 1][col] == 1)
{
copy1[row][col] = 0;
b = path_help(copy1, row - 1, col, count + 1);
}
else b = N*N;
if (maze[row][col + 1] == 1)
{
copy2[row][col] = 0;
c = path_help(copy2, row, col + 1, count + 1);
}
else c = N*N;
if (maze[row][col - 1] == 1)
{
copy3[row][col] = 0;
d = path_help(copy3, row, col - 1, count + 1);
}
else d = N*N;
return min(min(a, b),min( c, d));
}