1
\$\begingroup\$

Problem statement

Consider a matrix with \$n\$ rows and \$m\$ columns, where each cell contains either a \$0\$ or a \$1\$ and any cell containing a is called a filled cell. Two cells are said to be connected if they are adjacent to each other horizontally, vertically, or diagonally; in other words, cell \$[i][j]\$ is connected to cells \$[i-1][j-1]\$, \$[i-1][j]\$, \$[i-1][j+1]\$, \$[i][j-1]\$, \$[i][j+1]\$, \$[i+1][j-1]\$, \$[i+1][j]\$, and \$[i+1][j+1]\$, provided that the location exists in the matrix for that \$[i][j]\$.

If one or more filled cells are also connected, they form a region. Note that each cell in a region is connected to at least one other cell in the region but is not necessarily directly connected to all the other cells in the region.

Task

Given an \$n\$ x \$m\$ matrix, find and print the number of cells in the largest region in the matrix. Note that there may be more than one region in the matrix.

Input Format

The first line contains an integer, \$n\$, denoting the number of rows in the matrix. The second line contains an integer, \$m\$, denoting the number of columns in the matrix. Each line \$i\$ of the \$n\$ subsequent lines contains \$m\$ space-separated integers describing the respective values filling each row in the matrix.

Constraints

\$0 < n, m < 10\$

Output Format

Print the number of cells in the largest region in the given matrix.

Sample Input

4

4

1 1 0 0

0 1 1 0

0 0 1 0

1 0 0 0

Sample Output

5

Explanation

The diagram below depicts two regions of the matrix; for each region, the component cells forming the region are marked with an \$X\$:

X X 0 0     1 1 0 0

0 X X 0     0 1 1 0

0 0 X 0     0 0 1 0

1 0 0 0     X 0 0 0

The first region has five cells and the second region has one cell. Because we want to print the number of cells in the largest region of the matrix, we print \$5\$.

Difficulty: Medium

Introduction of algorithm:

I reviewed my last practice using queue and then made a few changes on the C# code, and like to get some input how to set up several checkpoints to expedite the coding and debugging, for example, I added a variable DebugInfo this time to help me track connected region with each cell's \$[i][j]\$ values, how many connected regions and many other intermediate results. About the design of using queue, I added unvisited node to the queue first and then mark the node visited.

Please share your ideas how to make C# algorithm using queue better one. If you have a lot of C# experience, what advice you like to share for this practice, cut time and ensure the quality etc.

The code passes all the cases on hackerank.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace connectedCellMay11
{
    /*
     * Problem statement:
     * https://www.hackerrank.com/challenges/connected-cell-in-a-grid
     */
    class Program
    {
        static void Main(string[] args)
        {
            ProcessConnectedCellInGrid(); 

            //RunSampleTestcase();
        }

        public static void ProcessConnectedCellInGrid()
        {
            int rows = Convert.ToInt32(Console.ReadLine());
            int cols = Convert.ToInt32(Console.ReadLine());

            int[,] matrix = new int[rows, cols];

            for (int i = 0; i < rows; i++)
            {
                string[] data = Console.ReadLine().Split(' ');

                for (int j = 0; j < cols; j++)
                    matrix[i, j] = Convert.ToInt32(data[j]);
            }

            Console.WriteLine(GetNumberOfCellsInLargestRegion(matrix, rows, cols));
        }

        /*
         * HackerRank problem statement comes with a sample test case. 
         * sample input
         * 4
         * 4
         * 1 1 0 0
         * 0 1 1 0
         * 0 0 1 0 
         * 1 0 0 0
         * sample output: 5
         */
        static void RunSampleTestcase()
        {
            int rows = 4;
            int cols = 4;

            string[] matrix = new string[] { "1 1 0 0", "0 1 1 0", "0 0 1 0", "1 0 0 0" };

            int[,] arr = new int[rows, cols];

            for (int i = 0; i < rows; i++)
            {
                string[] colA = matrix[i].Split(' ');

                for (int j = 0; j < cols; j++)
                    arr[i, j] = Convert.ToInt32(colA[j]);
            }

            Debug.Assert(GetNumberOfCellsInLargestRegion(arr, rows, cols) == 5);
        }

        /*
         * Task: find and print the number of cells in the largest region in the matrix
         */
        public static int GetNumberOfCellsInLargestRegion(int[,] matrix, int rows, int cols)
        {
            int max = Int32.MinValue;

            for (int row = 0; row < rows; row++)
                for (int col = 0; col < cols; col++)
                {
                    if (matrix[row, col] == 1)
                    {
                        int value = TraverseRegionAndCount(matrix, rows, cols, row, col);
                        max = value > max ? value : max;
                    }
                }

            return max;
        }

        /*
         * spec:
         * a node is connected to 8 neighbors
         * left, right, up and down, also cross directions: 
         * left-top, right-top, left-bottom, right-bottom
         * if the location exists in the matrix for that [i][j]
         * 
         * Task: Visit all unvisited connected neighbors using a queue, 
         * mark the cell as visited by setting the value 0. 
         * 
         * design to use queue properly in the following: 
         * only add unvisited node to the queue, add to queue first, 
         * and then update the node as a visited one.
         * 
         * It is a BFS algorithm. 
         */
        private static int TraverseRegionAndCount(
            int[,] matrix,
            int rows,
            int cols,
            int startX,
            int startY)
        {
            Queue<int> queue = new Queue<int>();
            queue.Enqueue(GetKeyNumber(startX, startY));
            matrix[startX, startY] = 0;

            IList<string> DebugInfo = new List<string>(); 

            int count = 0;
            while (queue.Count > 0)
            {
                int key = (int)queue.Dequeue();

                int visitingCellRow = key / 10;
                int visitingCellCol = key % 10;

                for (int row = -1; row <= 1; row++)
                {
                    for (int col = -1; col <= 1; col++)
                    {
                        int neighborRow = row + visitingCellRow;
                        int neighborCol = col + visitingCellCol;

                        if (BoundaryCheck(neighborRow, neighborCol, rows, cols) &&
                            matrix[neighborRow, neighborCol] == 1)
                        {
                            matrix[neighborRow, neighborCol] = 0;
                            queue.Enqueue(GetKeyNumber(neighborRow, neighborCol));
                        }
                    }
                }

                DebugInfo.Add(visitingCellRow + "-" + visitingCellCol); 
                count++;
            }

            return count;
        }

        /*
         * check the boundary of matrix 
         */
        private static bool BoundaryCheck(int row, int col, int rows, int cols)
        {
            if ((row >= 0 && row < rows) && (col >= 0 && col < cols))
                return true;
            else
                return false;
        }

        /*
         * key should be unique, since 0 < n, m < 10, 
         * the mapping function 10 * row + col will uniquely define the key value 
         * for matrix[row, col], any row, col in the range of (0,10). 
         * In other words, key is a two-digit integer 
         * leftmost digit  - row, 
         * rightmost digit - col
         */
        private static int GetKeyNumber(int row, int col)
        {
            return 10 * row + col;
        }
    }
}
\$\endgroup\$
3
\$\begingroup\$

BoundaryCheck

If you have an if...else construct where you return true if the if condition is met and false otherwise, you can simplify this by just returning the result of the condition, like so:

private static bool BoundaryCheck(int row, int col, int rows, int cols)
{
    return row >= 0 && row < rows && col >= 0 && col < cols;
}  

There is no need to enclose the condition with () (although you can if like).


ProcessConnectedCellInGrid

int rows = Convert.ToInt32(Console.ReadLine());
int cols = Convert.ToInt32(Console.ReadLine());  

This is a no go. Never ever trust the user's input. If the user enters a value that isn't an int, your code will blow up in the user's face. Therefore, you must always validate user input. Here, you should use the TryParse() method, which returns true if the passed string can be parsed to an int. It returns false if the parse is unsuccessful, and you will then need to handle this error (e.g., by displaying a message to the user and asking them to try entering the value again).


Although they may be technically optional, omitting braces { } for single-statement if constructs or for loops is a bad habit that you should break. Omitting braces can lead to serious and hard-to-track-down bugs. I would like to encourage you to always use them. This will make your code less error-prone and better structured.


Ternary expressions like

max = value > max ? value : max;

are a nice to have, but should be used judiciously. In my opinion, it would be much easier to read with a simple if condition, like so:

if (value > max)
{
    max = value;
}  

Easier reading of the code is a goal you want to achieve because this will either help you or Sam the maintainer to find bugs or add functionality easily because you or Sam will see at first glance what it is about (you don't need to stress your brain by figuring out what some lines of code are supposed to do).

\$\endgroup\$
  • \$\begingroup\$ I suppose ternary expressions are just something you get used to reading. I don't find one form any easier to read than the other, personally. And in the case where you needed to add an else block, I'd say that a ternary expression would be even easier to read, since there is only a single assignment to max. But this is all subjective preference. Otherwise, some very good points made here about style and readability. \$\endgroup\$ – Cody Gray Jan 2 '17 at 11:30
2
\$\begingroup\$
int[,] matrix = new int[rows, cols];

In general multidimensional arrays like this one should be avoided. They are easy to work with but at the cost of the performance. For this small matrix it probably doesn't matter but so that you know. Instead the faster jagged arrays should be used.

int[][] matrix = new int[rows][];
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.