Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- namespace prolazak_kroz_lavirint___backtracking
- {
- internal class Program
- {
- static void Main(string[] args)
- {
- string[,] maze = new string[,]
- {
- { "", "X", "X", "X", "X" },
- { "", "X", "", "", "" },
- { "", "", "", "", "" },
- { "", "X", "", "X", "" },
- };
- int xStart = 1;
- int yStart = 0;
- int xEnd = 2;
- int yEnd = 4;
- int[,] moves = new int[,]
- {
- {-1, 0 }, //left
- {0, -1 }, //up
- {1, 0 }, //right
- {0, 1 }, //down
- };
- maze[xStart, yStart] = ".";
- bool gotOut = false;
- //GetOutOfTheMaze(maze, moves, xStart, yStart, xEnd, yEnd, ref gotOut);//first solution, not fastest
- int numSteps = 0;
- int minSteps = int.MaxValue;
- //string[,] shortestSolution = new string[,];
- GetOutOfTheMazeShortest(maze, moves, xStart, yStart, xEnd, yEnd, numSteps, ref minSteps);
- }
- private static void GetOutOfTheMaze(string[,] maze, int[,] moves, int x, int y, int xEnd, int yEnd, ref bool gotOut)
- {
- if (x == xEnd && y == yEnd)
- {
- outputMatrix(maze);
- gotOut = true;
- return;
- }
- for (int i = 0; i <= moves.GetLength(0) - 1; i++)
- {
- int newX = x + moves[i, 0];
- int newY = y + moves[i, 1];
- if (ValidMove(newX, newY, maze) && !gotOut)
- {
- maze[newX, newY] = ".";//add new move
- GetOutOfTheMaze(maze, moves, newX, newY, xEnd, yEnd, ref gotOut);
- maze[newX, newY] = "";//erase that(new) move
- }
- }
- }
- private static void GetOutOfTheMazeShortest(string[,] maze, int[,] moves, int x, int y, int xEnd, int yEnd, int numSteps, ref int minSteps)
- {
- if (x == xEnd && y == yEnd)
- {
- if (minSteps < numSteps)
- {
- outputMatrix(maze);
- minSteps = numSteps;
- }
- return;
- }
- for (int i = 0; i <= moves.GetLength(0) - 1; i++)
- {
- int newX = x + moves[i, 0];
- int newY = y + moves[i, 1];
- if (ValidMove(newX, newY, maze))
- {
- maze[newX, newY] = ".";//add new move
- GetOutOfTheMazeShortest(maze, moves, newX, newY, xEnd, yEnd);
- maze[newX, newY] = "";//erase that(new) move
- }
- }
- }
- private static bool ValidMove(int newX, int newY, string[,] maze)
- {
- return newX >= 0 && newX <= maze.GetLength(0) - 1 && newY >= 0 && newY <= maze.GetLength(1) - 1 && maze[newX, newY] == "";
- }
- private static void outputMatrix(string[,] maze)
- {
- for (int i = 0; i <= maze.GetLength(0) - 1; i++)
- {
- for (int j = 0; j <= maze.GetLength(1) - 1; j++)
- {
- Console.Write(maze[i, j].PadLeft(2));
- }
- Console.WriteLine();
- }
- Console.WriteLine();
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement