Advertisement
TimmyChannel

6

Apr 16th, 2024
629
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.24 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. public class ChessBoard {
  5.     public static void Main() {
  6.         int n = int.Parse(Console.ReadLine().Trim());
  7.         char[,] board = new char[n, n];
  8.         (int, int) start = (0, 0), finish = (0, 0);
  9.        
  10.         for (int i = 0; i < n; i++) {
  11.             string line = Console.ReadLine().Trim();
  12.             for (int j = 0; j < n; j++) {
  13.                 board[i, j] = line[j];
  14.                 if (board[i, j] == 'S') start = (i, j);
  15.                 else if (board[i, j] == 'F') finish = (i, j);
  16.             }
  17.         }
  18.        
  19.         int result = BFS(board, start, finish, n);
  20.         Console.WriteLine(result);
  21.     }
  22.  
  23.     private static int BFS(char[,] board, (int, int) start, (int, int) finish, int n) {
  24.         var directionsKing = new int[,] { {1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
  25.         var directionsKnight = new int[,] { {1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1} };
  26.         var queue = new Queue<(int, int, char, int)>();
  27.         var visited = new HashSet<(int, int, char)>();
  28.  
  29.         queue.Enqueue((start.Item1, start.Item2, 'K', 0)); // Start as a knight
  30.         visited.Add((start.Item1, start.Item2, 'K'));
  31.  
  32.         while (queue.Count > 0) {
  33.             var (x, y, type, moves) = queue.Dequeue();
  34.             if (x == finish.Item1 && y == finish.Item2) return moves;
  35.  
  36.             int[,] directions = type == 'K' ? directionsKnight : directionsKing;
  37.  
  38.             for (int i = 0; i < directions.GetLength(0); i++) {
  39.                 int newX = x + directions[i, 0];
  40.                 int newY = y + directions[i, 1];
  41.                 if (newX >= 0 && newY >= 0 && newX < n && newY < n && board[newX, newY] != 'W') {
  42.                     char newType = type;
  43.                     if (board[newX, newY] == 'K') newType = 'K';
  44.                     else if (board[newX, newY] == 'G') newType = 'G';
  45.                    
  46.                     if (!visited.Contains((newX, newY, newType))) {
  47.                         visited.Add((newX, newY, newType));
  48.                         queue.Enqueue((newX, newY, newType, moves + 1));
  49.                     }
  50.                 }
  51.             }
  52.         }
  53.  
  54.         return -1;
  55.     }
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement