Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created March 30, 2018 19:26
Show Gist options
  • Save jianminchen/d4eeb613a3ffffcac9635d4e9b724a95 to your computer and use it in GitHub Desktop.
Save jianminchen/d4eeb613a3ffffcac9635d4e9b724a95 to your computer and use it in GitHub Desktop.
Island count - using queue - I wrote a bug on line 47 and 50 to mix visitRow and visitCol with startRow and startCol. Next time it is important to declare new variables for visitRow, visitCol, otherwise I may mix things together. Build a good habit.
using System;
using System.Collections.Generic;
class Solution
{
public static int GetNumberOfIslands(int[,] binaryMatrix)
{
if(binaryMatrix == null)
return 0;
var rows = binaryMatrix.GetLength(0);
var columns = binaryMatrix.GetLength(1);
int countIsland = 0;
for(int row = 0; row < rows; row++)
{
for(int col = 0 ; col < columns; col++)
{
var current = binaryMatrix[row, col];
if(current != 1)
continue;
visitNeighbors(binaryMatrix, row, col);
countIsland++;
}
}
return countIsland;
}
private static void visitNeighbors(int[,] matrix, int startRow, int startCol)
{
var queue = new Queue<int[]>();
queue.Enqueue(new int[]{startRow, startCol});
while(queue.Count > 0)
{
var visitNode = queue.Dequeue();
var visitRow = visitNode[0];
var visitCol = visitNode[1];
matrix[visitRow, visitCol] = -1; // mark visited
pushNeighborToQueue(queue, matrix, visitRow, visitCol - 1); // left
pushNeighborToQueue(queue, matrix, visitRow, visitCol + 1); // right
pushNeighborToQueue(queue, matrix, visitRow - 1, visitCol); // up
pushNeighborToQueue(queue, matrix, visitRow + 1, visitCol); // down
}
}
private static void pushNeighborToQueue(Queue<int[]> queue, int[,] matrix, int startRow, int startCol)
{
var rows = matrix.GetLength(0);
var columns = matrix.GetLength(1);
if(startRow < 0 || startRow >= rows || startCol < 0 || startCol >= columns || matrix[startRow, startCol] != 1)
{
return;
}
queue.Enqueue(new int[]{startRow, startCol});
}
static void Main(string[] args)
{
}
}
/*
0 -1 0 -1 0
0 0 -1 -1 -1
C 0 0 -1 0
0 D -1 0 0
E 0 -1 0 F
countOfIsland 1 - A
1 - B
6 - A, B, C, D, E, F
BFS search / queue ->
*/
@jianminchen
Copy link
Author

I was lazy and do not declare two variables visitRow and visitCol, and then I mix startRow with visiitRow, startCol with visitCol. I wrote the code and forgot to push four neighbors into queue.
I finished the coding in less than 17 minutes, and I failed 3 test cases. It took me one minute to find the bug from line 47 to line 50. I fixed it in less than one minute.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment