Advertisement
Filip13

find bigest island - backtracking, recursion

Apr 23rd, 2024
501
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.88 KB | Source Code | 0 0
  1. using System;
  2.  
  3. namespace islands
  4. {
  5.     internal class Program
  6.     {
  7.         static void Main(string[] args)
  8.         {
  9.             // 0 - sea, 1 - unknown teritory
  10.             int[,] sea = new int[,]
  11.                 {
  12.                     { 1, 0, 1, 0, 0, 0, 1, },
  13.                     { 0, 0, 1, 1, 1, 0, 1, },
  14.                     { 1, 1, 1, 0, 0, 0, 1, },
  15.                     { 0, 0, 1, 1, 0, 1, 1, },
  16.                     { 0, 0, 0, 0, 0, 1, 1, },
  17.                     { 1, 1, 0, 0, 1, 1, 1, },
  18.                     { 0, 1, 0, 0, 0, 0, 0, },
  19.                 };
  20.  
  21.             //biggestIsland description
  22.             int sizeBI = 0;
  23.             int signBI = 0;
  24.  
  25.             //marking first island with number(2)
  26.             int sign = 2;
  27.  
  28.             for (int row = 0; row < sea.GetLength(0); row++)
  29.             {
  30.                 for (int column = 0; column < sea.GetLength(1); column++)
  31.                 {
  32.                     if (sea[row, column] == 1)
  33.                     {
  34.                         int islandSize = 0;
  35.                         MarkIsland(sea, row, column, sign, ref islandSize);
  36.  
  37.                         if (islandSize > sizeBI)
  38.                         {
  39.                             sizeBI = islandSize;
  40.                             signBI = sign;
  41.                         }
  42.  
  43.                         sign++;
  44.                     }
  45.                 }
  46.             }
  47.  
  48.             Console.WriteLine($"Biggest island is {signBI}, with size: {sizeBI}");
  49.             OutputIsland(sea);
  50.         }
  51.  
  52.         private static void MarkIsland(int[,] sea, int row, int column, int currentSign, ref int islandSize)
  53.         {
  54.             if (ValidField(sea, row, column) && FoundIsland(sea, row, column))
  55.             {
  56.                 sea[row, column] = currentSign;
  57.                 islandSize++;
  58.  
  59.                 MarkIsland(sea, row - 1, column, currentSign, ref islandSize);//up
  60.                 MarkIsland(sea, row + 1, column, currentSign, ref islandSize);//down
  61.                 MarkIsland(sea, row, column - 1, currentSign, ref islandSize);//left
  62.                 MarkIsland(sea, row, column + 1, currentSign, ref islandSize);//right
  63.             }
  64.  
  65.         }
  66.  
  67.         private static bool FoundIsland(int[,] sea, int row, int column)
  68.         {
  69.             return sea[row, column] == 1;
  70.         }
  71.  
  72.         private static bool ValidField(int[,] sea, int row, int column)
  73.         {
  74.             return row >= 0 && row < sea.GetLength(0) && column >= 0 && column < sea.GetLength(1);
  75.         }
  76.  
  77.         private static void OutputIsland(int[,] sea)
  78.         {
  79.             for (int row = 0; row < sea.GetLength(0); row++)
  80.             {
  81.                 for (int column = 0; column < sea.GetLength(1); column++)
  82.                 {
  83.                     Console.Write($"{sea[row, column],7}");
  84.                 }
  85.                 Console.WriteLine();
  86.             }
  87.         }
  88.  
  89.     }
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement