제출 #1148101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1148101		alejandrov	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	91 ms	14428 KiB

joi2019_ho_t4

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class joi2019_ho_t4 {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int numOfColumns = scanner.nextInt();
    boolean[][] cellsOccupied = new boolean[2][numOfColumns];
    for (boolean[] row :
        cellsOccupied) {
      Arrays.fill(row, false);
    }

    HashMap<String, Coordinate> coordinatesCoins = new HashMap<>();

    int result = 0;
    
    for (int i = 0; i < numOfColumns * 2; i++) {
      int x = scanner.nextInt();
      int y = scanner.nextInt();

      if (x >= 1 && x <= numOfColumns && y >= 1 && y <= 2) {
        cellsOccupied[y - 1][x - 1] = true;
      } else {
        coordinatesCoins.put(x + " " + y, new Coordinate(x, y));
      }
    }
    
    List<Coordinate> coordinates = new LinkedList<>(coordinatesCoins.values());

    for (Coordinate coordinate : coordinates) {
      int minimumDistance = Integer.MAX_VALUE;
      int minX = 0;
      int minY = 0;
      Coordinate current = coordinate;
      for (int emptySlot = 0; emptySlot < numOfColumns * 2; emptySlot++) {
        int coordY = emptySlot % 2;
        int coordX = emptySlot / 2;
        if (cellsOccupied[coordY][coordX])
          continue;

        int distance = current.getDistance(coordX + 1, coordY + 1);
        if (distance < minimumDistance) {
          minX = coordX;
          minY = coordY;
          minimumDistance = distance;
        }

        if (minimumDistance == 0)
          break;
      }

      //System.out.println(minimumDistance);
      result += minimumDistance;
      cellsOccupied[minY][minX] = true;
    }
    
    //System.out.println(coordinatesCoins);
    System.out.println(result);
  }

  static class Coordinate {
    int x;
    int y;

    public Coordinate(int x, int y) {
      this.x = x;
      this.y = y;
    }

    public int getDistance(int x2, int y2) {
      return Math.abs(x - x2) + Math.abs(y - y2);
    }

    @Override
    public String toString() {
      return x + " " + y;
    }
  }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63