Coding Challenge – Bodies of Water

Problem:

Write a program that first takes an integer N giving both the X and Y size, and then N number of lines. Each line will contain N space-delimited characters, 0, 1, or 2. These characters represent altitude on the map. Zero means water.

First, find the bodies of water. A body of water is a group of ‘0’s connected to each other either directly or diagonally.

For each body of water, count the number of cells that it occupies. Print to STDOUT the sizes of each body sorted from smallest to largest.

Solution:

View solution

Here are somethings that may be helpful: (1)this is a variation of a flood fill, (2) using -1 is a good way to mark parts of the water we already visited.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var matrixXY = Int32.Parse(Console.ReadLine());
            int[,] matrix = new int[matrixXY,matrixXY];
            ReadMatrix(ref matrix,matrixXY);
            var waterBodySizes = FindSortedBodiesOfWater(ref matrix,matrixXY);
            foreach(var size in waterBodySizes)
            {
                Console.WriteLine(size);
            }
        }
        
        private static void ReadMatrix(ref int[,] matrix,int size)
        {
            for(int i = 0; i < size; ++i)
            {
                var items = Console.ReadLine().Split(' ');
                for(int j = 0; j < items.Length; ++j)
                {
                    var num = Int32.Parse(items[j]);
                    matrix[i,j] = num;
                }
            }
        }
        
        private static List<int> FindSortedBodiesOfWater(ref int[,] map, int size)
        {
            List<int> sizesOfWaterBodies = new List<int>();
            for(int i = 0; i < size; ++i)
            {
                for(int j = 0; j < size; ++j)
                {
                    int waterBodySize = GetBodyOfWaterSize(ref map, size, i, j);
                    if(waterBodySize > 0)
                    {
                        sizesOfWaterBodies.Add(waterBodySize);
                    }
                }
            }
            sizesOfWaterBodies.Sort();
            return sizesOfWaterBodies;
        }
                                              
      private static int GetBodyOfWaterSize(ref int[,] map, int sizeOfMap, int x, int y)
      {
          int sizeOfWater = 0;
          if(map[x,y] == 0)
          {
              map[x,y] = -1;
              ++sizeOfWater;
              // north
              if(y - 1 >= 0)
              {
                  sizeOfWater += GetBodyOfWaterSize(ref map, sizeOfMap,x, y-1);
                  // northeast
                  if(x + 1 < sizeOfMap)
                  {
                      sizeOfWater += GetBodyOfWaterSize(ref map, sizeOfMap, x + 1, y - 1);
                  }
                  // northwest
                  if(x - 1 >= 0)
                  {
                      sizeOfWater += GetBodyOfWaterSize(ref map, sizeOfMap, x - 1, y - 1);
                  }
              }
              // east
              if(x + 1 < sizeOfMap)
              {
                  sizeOfWater += GetBodyOfWaterSize(ref map, sizeOfMap, x+1,y);
              }
              // south
              if(y + 1 < sizeOfMap)
              {
                  sizeOfWater += GetBodyOfWaterSize(ref map, sizeOfMap, x, y + 1);
                  // southeast
                  if(x + 1 < sizeOfMap)
                  {
                      sizeOfWater += GetBodyOfWaterSize(ref map, sizeOfMap, x + 1, y + 1);
                  }
                  // southwest
                  if( x - 1 >= 0)
                  {
                      sizeOfWater += GetBodyOfWaterSize(ref map, sizeOfMap, x - 1, y + 1);
                  }
              }
              // west
              if(x - 1 >= 0)
              {
                  sizeOfWater += GetBodyOfWaterSize(ref map, sizeOfMap, x - 1, y);
              }
          }
          return sizeOfWater;
      }
    }
}

Play with the solution online

Close solution

This entry was posted on Monday, October 16th, 2017 at 6:00 pm

Leave a Reply

Your email address will not be published. Required fields are marked *