Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 18, 2016 18:30
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/d434bcc59ebc8eb7c2cbb20c6f48ac06 to your computer and use it in GitHub Desktop.
Save jianminchen/d434bcc59ebc8eb7c2cbb20c6f48ac06 to your computer and use it in GitHub Desktop.
Connected Cell In a Grid - Hacker Rank - practice code and see if I can speed up
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace continuedCellsInaGrid
{
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().ToString();
int j=0;
foreach (char c in s)
{
//while(c=='0' || c=='1') // not while, causing timeout
if (c == '0' || c == '1')
{
arr[i,j] = (int)(c - '0');
j++;
}
}
}
Console.WriteLine(getMaxRegin(arr));
}
public static int getMaxRegin(int[,] arr)
{
int row = arr.GetLength(0);
int col = arr.GetLength(1);
int max = int.MinValue;
for(int i =0; i< row; i++)
for (int j = 0; j < col; j++)
{
int val = getCount(arr, i, j);
max = val > max? val: max;
}
return max;
}
private static int getCount(int[,] arr, int posX, int posY)
{
int row = arr.GetLength(0);
int col = arr.GetLength(1);
if (posX >= 0 && posX < row && posY >= 0 && posY < col && arr[posX,posY] == 1)
{
arr[posX, posY] = 2;
int count = 1;
for(int dr = -1; dr<=1; dr++)
for (int dc = -1; dc <= 1; dc++)
{
int tmpX = posX + dr;
int tmpY = posY + dc;
count += getCount(arr, tmpX, tmpY);
}
return count;
}
return 0;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment