Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created April 17, 2016 00:41
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/4f4d499599c015144e77e5016bd86912 to your computer and use it in GitHub Desktop.
Save jianminchen/4f4d499599c015144e77e5016bd86912 to your computer and use it in GitHub Desktop.
HackerRank - connected cell in a grid - DFS solution
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Solution
{
static void Main(string[] args)
{
int row = Convert.ToInt16(Console.ReadLine());
int col = Convert.ToInt16(Console.ReadLine());
int[][] arr = new int[row][];
for (int i = 0; i < row; i++)
arr[i] = new int[col];
for (int i = 0; i < row; i++)
{
string[] rowA = Console.ReadLine().Split(' ');
if (rowA.Length < col)
break;
for (int j = 0; j < col; j++)
arr[i][j] = Convert.ToInt16(rowA[j]);
}
Console.WriteLine(getMax(arr, row, col));
}
public static int getMax(int[][] arr, int m, int n)
{
bool[][] visited = new bool[m][];
for(int i=0;i<m;i++)
visited[i] = new bool[n];
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
visited[i][j] = false;
}
int max = 0;
IList<string> curList = new List<string>();
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
{
if (!visited[i][j])
{
int node = arr[i][j];
if (node == 1)
{
IList<string> list = new List<string>();
DFS(arr, i, j, visited, m + n, list);
if (list.Count > max)
{
curList = list;
max = list.Count;
}
}
}
}
return max;
}
private static void DFS(int[][] arr, int i, int j, bool[][] visited, int maxStep, IList<string> list)
{
int row = arr.Length;
int col = arr[0].Length;
if( i<row && i>=0 && j<col && j>=0 && maxStep >=0)
{
// node is 1 and not visited.
if (arr[i][j] == 1 && !visited[i][j])
{
visited[i][j] = true;
list.Add(i.ToString() + ";" + j.ToString());
DFS(arr, i - 1, j - 1, visited, maxStep - 1, list);
DFS(arr, i - 1, j, visited, maxStep - 1, list);
DFS(arr, i - 1, j + 1, visited, maxStep - 1, list);
DFS(arr, i, j - 1, visited, maxStep - 1, list);
DFS(arr, i, j + 1, visited, maxStep - 1, list);
DFS(arr, i + 1, j - 1, visited, maxStep - 1, list);
DFS(arr, i + 1, j, visited, maxStep - 1, list);
DFS(arr, i + 1, j + 1, visited, maxStep - 1, list);
}
else if(arr[i][j] == 0)
{
if (!visited[i][j])
visited[i][j] = true;
}
}
// 8 possible direction
// up left
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment