Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- import java.util.ArrayList;
- import java.util.HashMap;
- import java.util.stream.Collectors;
- public class RainfallChallenge
- {
- public static void main(String[] args)
- {
- Scanner input = new Scanner(System.in);
- // building the farm
- int size = input.nextInt();
- Farm farm = new Farm(size);
- // setting heights, creating fields
- for (int x = 0; x < size; x++)
- for (int y = 0; y < size; y++)
- farm.putField(x, y, new Field(input.nextInt()));
- // skynet addon: knows every field as key and maps to the list of all fields of its basin
- HashMap<Field, ArrayList<Field>> basins = new HashMap<Field, ArrayList<Field>>();
- for (int x = 0; x < size; x++)
- for (int y = 0; y < size; y++)
- groupFields(basins, farm.getField(x, y));
- // from lists of fields to sorted list of basin sizes
- System.out.println(
- new StringBuilder(
- basins.values()
- .stream()
- .distinct() // set of field lists
- .mapToInt(b -> b.size()) // to their number of fields
- .sorted()
- .boxed() // in bubble wrap
- .map(String::valueOf) // to String stream
- .collect(Collectors.joining(" "))).reverse()); // desired order
- }
- private static ArrayList<Field> groupFields(HashMap<Field, ArrayList<Field>> basins, Field field)
- {
- ArrayList<Field> basin;
- // end recursion: revisit field
- if(basins.containsKey(field))
- {
- return basins.get(field);
- }
- // end recursion: new basin
- else if(field.getLowestNeighbor() == field)
- {
- basin = new ArrayList<Field>();
- }
- // recursion: find basin of lowest neighbor
- else
- {
- basin = groupFields(basins, field.getLowestNeighbor());
- }
- basin.add(field);
- basins.put(field, basin);
- return basin;
- }
- }
- class Farm
- {
- private Field[][] fields;
- public Farm(int size)
- {
- fields = new Field[size][size];
- }
- public void putField(int x, int y, Field field)
- {
- fields[x][y] = field;
- // check all 4 neighbors
- field.setNeighbor(getField(x + 1, y));
- field.setNeighbor(getField(x - 1, y));
- field.setNeighbor(getField(x, y + 1));
- field.setNeighbor(getField(x, y - 1));
- }
- public Field getField(int x, int y)
- {
- try
- {
- return fields[x][y] != null ? fields[x][y] : NullField.instance;
- }
- catch (IndexOutOfBoundsException e)
- {
- return NullField.instance;
- }
- }
- }
- class Field
- {
- private int height;
- private Field lowestNeighbor;
- public Field(int height)
- {
- this.height = height;
- lowestNeighbor = this;
- }
- public void setNeighbor(Field neighbor)
- {
- if (neighbor.height < lowestNeighbor.height)
- {
- lowestNeighbor = neighbor;
- }
- else if (neighbor.lowestNeighbor.height > height)
- {
- neighbor.lowestNeighbor = this;
- }
- }
- public Field getLowestNeighbor()
- {
- return lowestNeighbor;
- }
- }
- class NullField extends Field
- {
- public static final NullField instance = new NullField();
- private NullField()
- {
- super(Integer.MAX_VALUE);
- }
- }
- // from lists of fields to sorted list of basin sizes
- System.out.println(
- new StringBuilder(
- basins.values()
- .stream()
- .distinct() // set of field lists
- .mapToInt(b -> b.size()) // to their number of fields
- .sorted()
- .boxed() // in bubble wrap
- .map(String::valueOf) // to String stream
- .collect(Collectors.joining(" "))).reverse()); // desired order
- public Field getField(int x, int y)
- {
- try
- {
- return fields[x][y] != null ? fields[x][y] : NullField.instance;
- }
- catch (IndexOutOfBoundsException e)
- {
- return NullField.instance;
- }
- }
- class NullField extends Field
- {
- public static final NullField instance = new NullField();
- private NullField()
- {
- super(Integer.MAX_VALUE);
- }
- }
- public void setNeighbor(Field neighbor)
- {
- // pffft, whatever
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement