Cześć, na studia muszę napisać program, który będzie symulował jak teren wypełnia się wodą.
Napisałem wersję jednowątkową, teraz muszę to zrównoleglić.
Nie wiem jednak jak skutecznie podzielić mapę na fragmenty tak, aby nie było race condition.
Próbowałem blokować obszary w tablicy o rozmiarze 3x3, ale nic z tego nie wyszło.
Znacie może jakiś algorytm, który opisuje mój problem?
Szukałem w Internecie, ale to co znajdywałem zazwyczaj odnosiło się obliczania ile jednostek wody można zmieścić w terenie.
Uprzedzam, że nie szukam gotowca, a zwykłego naprowadzenia na rozwiązanie.
Dana jest macierz kodująca mapę, w której liczby oznaczają wysokości.
Wylicz ile punktów w macierzy zajmują lądy i oceany, największą i średnią głębokość oceanu, przy założeniu, że oceany
powstają poprzez wpuszczenie X jednostek wody w określonym punkcie:
- Woda spływa w dół (jeżeli może, tj. jeżeli wysokość+ilość wody jest większa od sąsiadujących punktów).
- Możliwe jest, że w punkcie jest jedna jednostka wody, a obok punkt ma taką samą wysokość. Woda wówczas nie spływa.
- Jeżeli woda może spłynąć w kilka miejsc naraz, początkowo spływa po równo w każdą stronę.
internal sealed class SingleThreadAlgorithm : IAlgorithm
{
public void FillArea(Map map, Coordinates centralCoordinates, int waterUnitCount)
{
for (int i = waterUnitCount; i > 0; i--)
{
map[centralCoordinates].IncreaseWaterLevel();
}
Fill(map, centralCoordinates);
}
private void Fill(Map map, Coordinates centralCoordinates)
{
var centralPoint = map[centralCoordinates];
bool waterLevelDropped = true;
// Rozlewamy równo wodę do sąsiadów tak długo jak możemy(robimy kółeczka)
while(waterLevelDropped)
{
waterLevelDropped = FillAround(map, centralCoordinates, centralPoint);
}
}
private bool FillAround(Map map, Coordinates centralCoordinates, Point centralPoint)
{
bool waterLevelDropped = false;
var coordinates = new List<Coordinates>();
for (int i = -1; i < 2; i++)
{
for (int j = -1; j < 2; j++)
{
var neighbourCoordinates = new Coordinates(i + centralCoordinates.X, j + centralCoordinates.Y);
if (map.AreCoordinatesValid(neighbourCoordinates))
{
var neighbourPoint = map[neighbourCoordinates];
if (centralPoint.TotalLevel > neighbourPoint.TotalLevel + 1 && centralPoint.WaterLevel > 0)
{
centralPoint.DecreaseWaterLevel();
neighbourPoint.IncreaseWaterLevel();
coordinates.Add(neighbourCoordinates);
waterLevelDropped = true;
}
}
}
}
// Woda spływa z sąsiadów do ich sąsiadów(jeśli może)
foreach (var coordinate in coordinates)
{
Fill(map, coordinate);
}
return waterLevelDropped;
}
}
Input
Liczba jednostek wody: 20
Punkt startowy: 0,0
Mapa:
5,5,2,2,2
2,2,2,2,2
2,2,2,2,2
2,2,2,2,2
2,2,2,2,2
Output
Legenda - Wysokość: Wysokość terenu + Wysokość wody