Flood fill algorithm - count of island - mocking experience transcript

floodfill_island_mockingexperience.cs

/// neighbor left/ right, top,down 
/// 4 islands,  A, B, C, D, E, F six islands Flood fill algorithm
//  find first cell with value -> iterate row, col from 0, 0 
// value -> 1, BFS search, visit all cells in the island -> mark visited -> 2 , island increment
// -> continue to search value with 1, those visited node marked to 2 , make sure no visit
// check boundary check -> matrix go outside
// double for loop -> row, col, BFS -> queue
// return run time complexity
// node with 1, every at most 1 first 
// BFS -> go through -> 1 , each island visited once 
// O( n x m)
// extra space -> 
// 0 1A 0 1 0 
// 0 0 1 1B 1
// 1E 0 0 1 0 
// 0 1D 1 0 0 
// 1F 0 1 0 1C
//
using System;

class LearningExperience {
   static void Main(string[] args) {
      Console.WriteLine("Meet a new person and talk about flood fill algorithm");
   }
   
   public static int CountIsland(int[][] matrix)
   {
      if(matrix == null || matrix.Length == 0 || matrix[0].Length=0) return 0; 
      
      int rows = matrix.Length; 
      int cols = matrix[0].Length; 
      
      int islandCount = 0; 
      for(int row = 0 ; row < rows; row++)
      {
         for(int col = 0; col < cols; col++)
         {
            var current = matrix[row][col]; 
            
            if(current != 1) continue; 
            
            visitIslandBFS(matrix, row, col); 
            islandCount ++; 
         }
      }
      
      return islandCount; 
   }
   
   private static void visitIslandBFS(int[][] matrix, int row, int col)
   {
      Queue<string> queue = new Queue<string>(); 
      
      var key = encodeKey(row,col); 
      queue.enqueue(key); 
      
      while(queue.Count > 0)
      {
         var current = queue.Dequeue(); 
         var positions = current.Split("+"); 
         
         int visit_row = positions[0];
         int visit_col = positions[1]; 
         
         matrix[visit_row][visit_col] = 2; 
         
         // left 
         int left_row = visit_row; 
         int left_col = visit_col-1; 
         if(isInBoundary(matrix, left_row, left_col) && matrix[left_row][left_col] == 1)
         {
            var neighborKey = encodeKey( left_row,left_col); 
            queue.enqueue(neighborKey); 
         }
         
         //right
         int right_row = visit_row; 
         int right_col = visit_col + 1; 
         if(isInBoundary(matrix, right_row, right_col) && matrix[right_row][right_col] == 1)
         {
            var neighborKey = encodeKey( right_row,right_col); 
            queue.enqueue(neighborKey); 
         }
         
         // top
         int top_row = visit_row - 1; 
         int top_col = visit_col ; 
         if(isInBoundary(matrix, top_row, top_col) && matrix[top_row][top_col] == 1)
         {
            var neighborKey = encodeKey( top_row,top_col); 
            queue.enqueue(neighborKey); 
         }
         
         // bottom
         int bottom_row = visit_row + 1; 
         int bottom_col = visit_col; 
         if(isInBoundary(matrix, bottom_row, bottom_col) && matrix[bottom_row][bottom_col] == 1)
         {
            var neighborKey = encodeKey( bottom_row,bottom_col); 
            queue.enqueue(neighborKey); 
         }
           
         
      }
   }
   
   private static string encodeKey(int row, int col)
   {
      return row +"+"+ col;
   }
   private static isInBoundary(int[][] matrix, int row, int col) 
   {
      int rows = matrix.Length; 
      int cols = matrix[0].Length; 
      
      return (row >= 0 && row < rows && col >=0 && col < cols); 
   }
}