SHARE
TWEET

ShortestPathInLabyrinth

a guest Aug 28th, 2014 274 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. class ShortestPath
  5. {
  6.     static char[,] field = {
  7.                                {' ','*',' ',' ',' ','*','*','*','*','*'},
  8.                                {' ',' ',' ','*',' ',' ',' ',' ','*','*'},
  9.                                {' ','*','*','*',' ',' ','*','*','*','*'},
  10.                                {' ',' ',' ',' ','*',' ',' ',' ',' ','*'},
  11.                                {' ',' ',' ',' ','*','*','*','*','*','*'},
  12.                            };
  13.  
  14.     //static char[,] field = {
  15.     //                           {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
  16.     //                           {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
  17.     //                           {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
  18.     //                           {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
  19.     //                           {' ',' ',' ',' ',' ',' ',' ',' ',' ',' '},
  20.     //                       };
  21.  
  22.     static int height = field.GetLength(0);
  23.     static int width = field.GetLength(1);
  24.  
  25.     static List<FieldStep> openList = new List<FieldStep>();
  26.     static List<FieldStep> finalPath = new List<FieldStep>();
  27.  
  28.     static void Main()
  29.     {
  30.         int startRow = 0;
  31.         int startCol = 0;
  32.         FieldStep startStep = new FieldStep(startRow, startCol);
  33.  
  34.         int endRow = 3;
  35.         int endCol = 8;
  36.         FieldStep endStep = new FieldStep(endRow, endCol);
  37.  
  38.         FindShortestPath(startStep, endStep);
  39.  
  40.         PrintResult(endStep);
  41.     }
  42.  
  43.     //this is the method using the breadth first search algorithm
  44.     static void FindShortestPath(FieldStep startStep, FieldStep endStep)
  45.     {
  46.         openList.Add(startStep);
  47.  
  48.         while (openList.Count != 0)
  49.         {
  50.             //check if the current step is in the field
  51.             FieldStep currentStep = openList[0];
  52.  
  53.             if (currentStep.Row == endStep.Row && currentStep.Col == endStep.Col)
  54.             {
  55.                 while (currentStep.Parent != null)
  56.                 {
  57.                     finalPath.Add(currentStep);
  58.                     currentStep = currentStep.Parent;
  59.                 }
  60.             }
  61.  
  62.             openList.RemoveAt(0);
  63.             field[currentStep.Row, currentStep.Col] = 'V';
  64.  
  65.             //start adding the neighbours of the current step
  66.  
  67.             if (currentStep.Row - 1 >= 0 && field[currentStep.Row - 1, currentStep.Col] == ' ')
  68.             {
  69.                 FieldStep upNeigbour = new FieldStep(currentStep.Row - 1, currentStep.Col);
  70.                 upNeigbour.Parent = currentStep;
  71.                 openList.Add(upNeigbour);
  72.             }
  73.  
  74.             if (currentStep.Col + 1 < width && field[currentStep.Row, currentStep.Col + 1] == ' ')
  75.             {
  76.                 FieldStep rightNeighbour = new FieldStep(currentStep.Row, currentStep.Col + 1);
  77.                 rightNeighbour.Parent = currentStep;
  78.                 openList.Add(rightNeighbour);
  79.             }
  80.  
  81.             if (currentStep.Row + 1 < height && field[currentStep.Row + 1, currentStep.Col] == ' ')
  82.             {
  83.                 FieldStep downNeigbour = new FieldStep(currentStep.Row + 1, currentStep.Col);
  84.                 downNeigbour.Parent = currentStep;
  85.                 openList.Add(downNeigbour);
  86.             }
  87.  
  88.             if (currentStep.Col - 1 > 0 && field[currentStep.Row, currentStep.Col - 1] == ' ')
  89.             {
  90.                 FieldStep leftNeigbour = new FieldStep(currentStep.Row, currentStep.Col - 1);
  91.                 leftNeigbour.Parent = currentStep;
  92.                 openList.Add(leftNeigbour);
  93.             }
  94.  
  95.         }
  96.     }
  97.  
  98.     //this method will print the final result
  99.     static void PrintResult(FieldStep endStep)
  100.     {
  101.         Console.WriteLine("Path found!");
  102.         for (int i = finalPath.Count - 1; i >= 0; i--)
  103.         {
  104.             Console.WriteLine("Row: {0}, Col: {1}", finalPath[i].Row, finalPath[i].Col);
  105.  
  106.             if (finalPath[i].Row == endStep.Row && finalPath[i].Col == endStep.Col
  107.                 && i != 0)
  108.             {
  109.                 Console.WriteLine();
  110.                 Console.WriteLine("Path found!");
  111.             }
  112.         }
  113.         Console.WriteLine();
  114.     }
  115.  
  116. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top