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; } } }
Close solution