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:
[show_more more=”View solution” less=”Close 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.
[csharp]
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;
}
}
}
[/csharp]
[/show_more]