Created
April 20, 2017 17:15
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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