HackerRank: Connected Cell in a Grid - C# solution - using DFS

April 16, 2016

Practice one DFS algorithm this Saturday.

problem statement: connected cell in a grid


C# solution written by Julia:


Time spent:  4:48pm - 5:41pm 
20 minutes to think about design, 
30 minutes to write the code
Feeling: nervous when thinking about solution - DFS, it took more than 15 minutes
Study other submissions, and see if I can learn something, also figure out how to cut time to write the code. 

C# solution: 
Time spent: 60 minutes

1. Use Queue, intead of using recurisve calls, using 2 dimension array, excellent code to study.

Tips to learn: 
1. use integer as key: i*10+j
2. mark the visited node using value 2

2. Design the function to return a value 

Julia, people are smart, no need for extra bool array[row][col], just mark the visited node using a new value:

1. mark visited node using 'X'

3. use C# Tuple class, declare a shift array to get more organized. 8 neighbors nodes - go through array twice.


4. study the code


5. declare offset array for x and y - Julia likes the idea.

https://gist.github.com/jianminchen/737138aeb946961aded556181c06502e

Statistics:

1. 10 submissions, there are at least 2 of them using queue - Julia, you have to catch up this using queue!  <- write queue version, practice it 20 minutes, post your version down here!
2. 10 submission, 2-3 DFS algorithm return count <- easy way to track the count
3. Different ways to mark the node is visited.

Reviewed the algorithm on Nov. 16, 2016
- some one found the page through yahoo.com search.