Skip to content

Instantly share code, notes, and snippets.

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/11725341e9474e0503950616c9ad1848 to your computer and use it in GitHub Desktop.
Save jianminchen/11725341e9474e0503950616c9ad1848 to your computer and use it in GitHub Desktop.
HackerRank - Connected Cell In a Grid - using stack, using DFS
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConnectedCellInaGrid_May11_usingStack_usingDFS
{
class Program
{
static void Main(string[] args)
{
int rows = Convert.ToInt32(Console.ReadLine());
int cols = Convert.ToInt32(Console.ReadLine());
int[,] arr = new int[rows, cols];
for (int i = 0; i < rows; i++)
{
string[] strA = Console.ReadLine().Split(' ');
for (int j = 0; j < cols; j++)
arr[i, j] = Convert.ToInt32(strA[j]);
}
Console.WriteLine(connectedCells(arr, rows, cols));
}
public static int connectedCells(int[,] arr, int rows, int cols)
{
int max = Int32.MinValue;
for(int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++)
{
if (arr[i, j] == 1)
{
int value = connectedCells_usingDFS_stack(arr, rows, cols, i, j);
max = value > max ? value : max;
}
}
return max;
}
private static int connectedCells_usingDFS_stack(int[,] arr, int rows, int cols, int startX, int startY)
{
Stack<int> stack = new Stack<int>();
arr[startX, startY] = 0;
stack.Push(calculatedKey(startX, startY));
int count = 0;
while (stack.Count > 0)
{
int key = (Int32)stack.Pop();
int tmpX = key / 10;
int tmpY = key % 10;
for(int i=-1; i<= 1; i++)
for (int j = -1; j <= 1; j++)
{
int neighbor_X = tmpX + i;
int neighbor_Y = tmpY + j;
if (isInBound(neighbor_X, neighbor_Y, rows, cols) && arr[neighbor_X, neighbor_Y] == 1)
{
arr[neighbor_X, neighbor_Y] = 0;
stack.Push(calculatedKey(neighbor_X, neighbor_Y));
}
}
count++;
}
return count;
}
private static bool isInBound(int x, int y, int rows, int cols)
{
return (x >= 0 && x < rows) && (y >= 0 && y < cols);
}
private static int calculatedKey(int startX, int startY)
{
return startX * 10 + startY;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment