Created
March 30, 2018 19:26
-
-
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.
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 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 -> | |
*/ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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.