Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 20, 2017 17:15
Show Gist options
  • Save jianminchen/164bb8d787d9bbf712f8faeb5ce2ac16 to your computer and use it in GitHub Desktop.
Save jianminchen/164bb8d787d9bbf712f8faeb5ce2ac16 to your computer and use it in GitHub Desktop.
Flood fill - count island - code review - make the code less verbose, extra a visit neighbor function - four directions neighbors
using System;
using System.Collections.Generic;
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 = Array.ConvertAll(current.Split('+'), int.Parse); // decode the key
int visit_row = positions[0];
int visit_col = positions[1];
matrix[visit_row][visit_col] = 2;
// left
visit(matrix, visit_row, visit_col, 0, -1, queue);
//right
visit(matrix, visit_row, visit_col, 0, 1, queue);
// top
visit(matrix, visit_row, visit_col, -1, 0, queue);
// bottom
visit(matrix, visit_row, visit_col, 1, 0, queue);
}
}
/// <summary>
/// visit function is to visit the neighbor nodes in four directions, left, right, top and bottom
/// </summary>
/// <param name="matrix"></param>
/// <param name="row"></param>
/// <param name="col"></param>
/// <param name="incrementX"></param>
/// <param name="incrementY"></param>
private static void visit(int[][] matrix, int row, int col, int incrementX, int incrementY, Queue<string> queue)
{
int neighbor_row = row + incrementX;
int neighbor_col = col + incrementY;
if(isInBoundary(matrix, neighbor_col, neighbor_col)
{
var neighborKey = encodeKey(neighbor_row, neighbor_col);
queue.Enqueue(neighborKey);
}
}
private static string encodeKey(int row, int col)
{
return row +"+"+ col;
}
private static bool 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);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment