Problem: You are given a two dimensional bit array(elements are 0 or 1). Find number of islands in this array. One island is defined as all elemnts which are 1, including neighbours(with or without diagonals). Or Array Islands problem.

// This is a given Array Array TwoDimArray; // Create three variables //1 This is a boolean array to remember what you scanned already Array MyOwnArray; // to remember the width (calling array.Size every time - I dont like- Dont believe compiler :) ) int width; // to remember the height of array int height;

// Here I populate some values to the array label1.Text = ""; TwoDimArray = Array.CreateInstance(typeof(Int32), 9, 9); for (int i = 0; i < TwoDimArray.GetLength(0); i++) { for (int j = 0; j < TwoDimArray.GetLength(1); j++) { TwoDimArray.SetValue((i * j) % 5 % 2, i, j); } } // To see what we populated for (int i = 0; i < TwoDimArray.GetLength(0); i++) { for (int j = 0; j < TwoDimArray.GetLength(1); j++) { label1.Text += TwoDimArray.GetValue(i,j).ToString(); } label1.Text += "\n\r"; } // Here is a lovely thing... // Look at TwoDimArray.SetValue((i * j) % 5 % 2, i, j); // Just replace (i * j) % 5 % 2 // with (i+j ) %2 // or with (i+j ) %2 // or with (i*j )%3 %2 // or with (i*j )%7 %2 // This is to get lot of variations during testing...

// Prepare your variables width,height,scanningArray width = TwoDimArray.GetLength(0); height = TwoDimArray.GetLength(1); MyOwnArray = Array.CreateInstance(typeof(Boolean), width, height); for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { MyOwnArray.SetValue(false, i, j); } }

// Here goes the main call int answer = 0; for (int i = 0; i < width; i++) { for (int j = 0; j < width; j++) { //ignore if you already scanned if( ( ( (bool)MyOwnArray.GetValue(i, j) ) == false) && ( ((int)TwoDimArray.GetValue(i, j)) != 0) ) { // true/fa;se in third argument will include or exclude diagonals as neghbours sweepneighbours(i, j,true); answer++; } } } label3.Text = answer.ToString();

private void sweepneighbours(int iii, int jjj,bool diag ) { if ((iii < width) && (jjj < height)) { //sweep self if (((int)TwoDimArray.GetValue(iii, jjj)) != 0) { // This is an important step -- otherwise we will endup recusive call for neighbours MyOwnArray.SetValue(true, iii, jjj); //sweep top left if ( diag&& ((iii - 1) > -1) && ((jjj - 1) > -1) && ((bool)MyOwnArray.GetValue(iii - 1, jjj - 1) == false ) && (((int)TwoDimArray.GetValue(iii - 1, jjj - 1)) != 0)) { sweepneighbours(iii - 1, jjj - 1, diag); } //sweep top == Already done if ( ((jjj - 1) > -1) && ((bool)MyOwnArray.GetValue(iii, jjj - 1) == false) && (((int)TwoDimArray.GetValue(iii, jjj - 1)) != 0)) { sweepneighbours(iii, jjj - 1, diag); } //sweep topright == Already done if ( diag&& ((iii + 1) < width) && ((jjj - 1) > -1) && ((bool)MyOwnArray.GetValue(iii+1, jjj - 1) == false) && (((int)TwoDimArray.GetValue(iii + 1, jjj - 1)) != 0)) { sweepneighbours(iii + 1, jjj - 1, diag); } //sweep left == Already done if ( ((iii - 1) > -1) && ((bool)MyOwnArray.GetValue(iii - 1, jjj) == false) && (((int)TwoDimArray.GetValue(iii - 1, jjj)) != 0)) { sweepneighbours(iii - 1, jjj, diag); } //sweep right if ( ((iii + 1) < width) && ((bool)MyOwnArray.GetValue(iii + 1, jjj) == false) && (((int)TwoDimArray.GetValue(iii + 1, jjj)) != 0)) { sweepneighbours(iii + 1, jjj, diag); } //sweep bottomleft if ( diag&& ((iii - 1) > -1) && ((jjj + 1) < height) && ((bool)MyOwnArray.GetValue(iii - 1, jjj + 1) == false) && (((int)TwoDimArray.GetValue(iii - 1, jjj + 1)) != 0)) { sweepneighbours(iii - 1, jjj + 1, diag); } //sweep bottom if ( ((jjj + 1) < width) && ((bool)MyOwnArray.GetValue(iii, jjj + 1) == false) && (((int)TwoDimArray.GetValue(iii, jjj + 1)) != 0)) { sweepneighbours(iii, jjj + 1, diag); } //sweep bottom right if ( diag&& ((iii + 1) < width) && ((jjj + 1) < height) && ((bool)MyOwnArray.GetValue(iii + 1 , jjj + 1) == false) && (((int)TwoDimArray.GetValue(iii + 1, jjj + 1)) != 0)) { sweepneighbours(iii + 1, jjj + 1, diag); } } } }

Lot to write here... 1) this is not a very efficient -- because I could have done MyOwnArray.SetValue(true,blah!!,blah!!) at many places above to save the processor. 2) problem asked for boolean array and I used a int array -- started lazy Notes: If diagonal are included, A typical chessboard is treated as one island If diagonals are excluded chess board will have 32 islands Happy programming.....

What is the complexity of this implementation?

good one I was looking for solution to this problem for long. got good direction for this. My 5 points for the idea

Here is a simplified version, little more readable. This one does not count diagonal elements as neighbors. using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ArrayIslands { class Program { static void Main(string[] args) { int[,] x = new int[4, 4] { {1,0,0,1}, {0,0,0,1}, {1,1,1,1}, {1,0,0,1} }; int y = CalculateIsland(x); Console.WriteLine("Total number of islands in this array are : "+y.ToString()); Console.Read(); } static int CalculateIsland(int[,] x) { if (x == null) { return -1; } int islandCount=0; int length = x.GetLength(0); int height = x.GetLength(1); for (int i = 0; i < length; i++) for (int j = 0; j < height; j++) { if (x[i, j] == 1) { sweepNeighbors(x,i, j); islandCount++; } } return islandCount; } static void sweepNeighbors(int[,] x, int ii, int jj) { int length = x.GetLength(0); int height = x.GetLength(1); if (ii < length && jj < height && x[ii, jj] == 1) { //mark this as visited x[ii, jj] = 2; //Look at 4 neighbors //Top if (ii >= 0 && jj >= 1 && x[ii, jj - 1] == 1) { sweepNeighbors(x, ii, jj - 1); } //Down if (ii >= 0 && jj < height - 1 && x[ii, jj + 1] == 1) { sweepNeighbors(x, ii, jj + 1); } //Left if (ii > 0 && jj >= 0 && x[ii - 1, jj] == 1) { sweepNeighbors(x, ii - 1, jj); } //Right if (ii < length - 1 && jj < height && x[ii + 1, jj] == 1) { sweepNeighbors(x,ii + 1, jj); } } } } }

This one does not use an additional boolean array, rather it performs operation on orginal array itself.