Advertisement
stanevplamen

Shortest path m3x BFS

Sep 21st, 2022
1,331
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 4.75 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. namespace BreadthFirstSearchExample
  5. {
  6.     public class BFSExample
  7.     {
  8.         class Point
  9.         {
  10.             public int xCoordinate { get; set; }
  11.             public int yCoordinate { get; set; }
  12.  
  13.             public Point(int x, int y)
  14.             {
  15.                 xCoordinate = x;
  16.                 yCoordinate = y;
  17.             }
  18.         }
  19.  
  20.         static char[,] matrix = new char[7, 7]
  21.         {
  22.             {' ',' ',' ','X','X','X','S'},
  23.             {' ','X',' ',' ',' ','X',' '},
  24.             {' ','X',' ','X','X','X',' '},
  25.             {' ','X',' ',' ',' ',' ',' '},
  26.             {' ','X',' ','X','X','X',' '},
  27.             {' ','X','X','X','X','X',' '},
  28.             {'E',' ',' ',' ',' ',' ',' '},
  29.         };
  30.  
  31.         static void BFS(Point startPoint)
  32.         {
  33.             Queue<Point> matrixPoints = new Queue<Point>();
  34.             matrixPoints.Enqueue(startPoint);
  35.             while (true)
  36.             {
  37.                 Point currentPoint = matrixPoints.Dequeue();
  38.                 if (currentPoint.xCoordinate - 1 >= 0)
  39.                 {
  40.                     if (matrix[currentPoint.xCoordinate - 1, currentPoint.yCoordinate] == 'E')
  41.                     {
  42.                         Console.WriteLine("We have found the shortest exit");
  43.                         return;
  44.                     }
  45.                     if (matrix[currentPoint.xCoordinate - 1, currentPoint.yCoordinate] == ' ')
  46.                     {
  47.                         matrix[currentPoint.xCoordinate - 1, currentPoint.yCoordinate] = '*';
  48.                         matrixPoints.Enqueue(new Point(currentPoint.xCoordinate - 1, currentPoint.yCoordinate));
  49.                     }
  50.                 }
  51.                 if (currentPoint.xCoordinate + 1 < matrix.GetLength(0))
  52.                 {
  53.                     if (matrix[currentPoint.xCoordinate + 1, currentPoint.yCoordinate] == 'E')
  54.                     {
  55.                         Console.WriteLine("We have found the shortest exit");
  56.                         return;
  57.                     }
  58.                     if (matrix[currentPoint.xCoordinate + 1, currentPoint.yCoordinate] == ' ')
  59.                     {
  60.                         matrix[currentPoint.xCoordinate + 1, currentPoint.yCoordinate] = '*';
  61.                         matrixPoints.Enqueue(new Point(currentPoint.xCoordinate + 1, currentPoint.yCoordinate));
  62.                     }
  63.                 }
  64.                 if (currentPoint.yCoordinate + 1 < matrix.GetLength(0))
  65.                 {
  66.                     if (matrix[currentPoint.xCoordinate, currentPoint.yCoordinate + 1] == 'E')
  67.                     {
  68.                         Console.WriteLine("We have found the shortest exit");
  69.                         return;
  70.                     }
  71.                     if (matrix[currentPoint.xCoordinate, currentPoint.yCoordinate + 1] == ' ')
  72.                     {
  73.                         matrix[currentPoint.xCoordinate, currentPoint.yCoordinate + 1] = '*';
  74.                         matrixPoints.Enqueue(new Point(currentPoint.xCoordinate, currentPoint.yCoordinate + 1));
  75.                     }
  76.                 }
  77.                 if (currentPoint.yCoordinate - 1 >= 0)
  78.                 {
  79.                     if (matrix[currentPoint.xCoordinate, currentPoint.yCoordinate - 1] == 'E')
  80.                     {
  81.                         Console.WriteLine("We have found the shortest exit");
  82.                         return;
  83.                     }
  84.                     if (matrix[currentPoint.xCoordinate, currentPoint.yCoordinate - 1] == ' ')
  85.                     {
  86.                         matrix[currentPoint.xCoordinate, currentPoint.yCoordinate - 1] = '*';
  87.                         matrixPoints.Enqueue(new Point(currentPoint.xCoordinate, currentPoint.yCoordinate - 1));
  88.                     }
  89.                 }
  90.                 Console.WriteLine();
  91.                 Console.WriteLine();
  92.                 PrintMatrix();
  93.             }
  94.         }
  95.  
  96.         static void PrintMatrix()
  97.         {
  98.             for (int i = 0; i < matrix.GetLength(0); i++)
  99.             {
  100.                 for (int j = 0; j < matrix.GetLength(1); j++)
  101.                 {
  102.                     if (matrix[i, j] == '*')
  103.                     {
  104.                         //Console.ForegroundColor = System.ConsoleColor.Red;
  105.                     }
  106.                     else
  107.                     {
  108.                         //Console.ForegroundColor = System.ConsoleColor.White;
  109.                     }
  110.                     Console.Write(matrix[i, j] + " ");
  111.                 }
  112.                 Console.WriteLine();
  113.             }
  114.         }
  115.  
  116.         public static void Main(string[] args)
  117.         {
  118.             Point startPoint = new Point(0, 6);
  119.             BFS(startPoint);
  120.         }
  121.     }
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement