Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 18, 2016 19:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/bd155e574b32ebb163455dad02fa76b1 to your computer and use it in GitHub Desktop.
Save jianminchen/bd155e574b32ebb163455dad02fa76b1 to your computer and use it in GitHub Desktop.
Connected Cell In a Grid - jagged array
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConnectedCellInAGrid3
{
class Program
{
static void Main(string[] args)
{
int row = Convert.ToInt32(Console.ReadLine());
int col = Convert.ToInt32(Console.ReadLine());
int[,] arr = new int[row, col];
for (int i = 0; i < row; i++)
{
string s = Console.ReadLine();
int j = 0;
foreach (char c in s)
{
if (c == '0' || c == '1')
{
arr[i, j++] = c - '0';
}
}
}
Console.WriteLine(getMaxRegion(arr));
}
public static int getMaxRegion(int[,] arr)
{
int row = arr.GetLength(0);
int col = arr.GetLength(1);
int max = Int32.MinValue;
for(int i=0;i< row; i++)
for (int j = 0; j < col; j++)
{
int val = getMaxRegion(arr, i, j);
if (val > max)
max = val;
}
return max;
}
private static int getMaxRegion(int[,] arr, int posX, int posY)
{
int row = arr.GetLength(0);
int col = arr.GetLength(1);
int count = 0;
if (posX >= 0 && posX < row && posY >= 0 && posY < col && arr[posX, posY] == 1)
{
arr[posX, posY] = 2;
count++;
// go through neighbor nodes - 8 neighbors
int[][] neighbors = new int[8][]{
// up row
new int[2]{-1, -1},
new int[2]{-1, 0},
new int[2]{-1, 1},
// same row
new int[2]{0, -1},
new int[2]{0, 1},
// down row
new int[2]{1, -1},
new int[2]{1, 0},
new int[2]{1, -1}
};
for (int i = 0; i < neighbors.Length; i++)
{
count += getMaxRegion(arr, posX + neighbors[i][0], posY + neighbors[i][1]);
}
}
return count;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment