Submission #1146278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146278		lucianaft	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	53 ms	11348 KiB

joi2019_ho_t4

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

class Coin {
  static class Position {
    int x, y, moves;

    Position(int x, int y, int moves) {
      this.x = x;
      this.y = y;
      this.moves = moves;
    }
  }

  public static int minMovesToTarget(int N, int[][] coins) {
    List<int[]> targets = new ArrayList<>();
    for (int x = 1; x <= N; x++) {
      for (int y = 1; y <= 2; y++) {
        targets.add(new int[]{x, y});
      }
    }

    int totalMoves = 0;
    boolean[] assigned = new boolean[2 * N];
    boolean[] occupied = new boolean[2 * N];

    for (int[] target : targets) {
      PriorityQueue<Position> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.moves));
      Set<String> visited = new HashSet<>();

      for (int i = 0; i < 2 * N; i++) {
        if (!assigned[i]) {
          pq.offer(new Position(coins[i][0], coins[i][1], 0));
          visited.add(coins[i][0] + "," + coins[i][1]);
        }
      }

      while (!pq.isEmpty()) {
        Position current = pq.poll();
        if (current.x == target[0] && current.y == target[1]) {
          for (int i = 0; i < 2 * N; i++) {
            if (!assigned[i] && coins[i][0] == current.x && coins[i][1] == current.y) {
              assigned[i] = true;
              totalMoves += current.moves;
              break;
            }
          }
          break;
        }

        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (int[] dir : directions) {
          int newX = current.x + dir[0];
          int newY = current.y + dir[1];
          String newState = newX + "," + newY;
          if (!visited.contains(newState)) {
            visited.add(newState);
            pq.offer(new Position(newX, newY, current.moves + 1));
          }
        }
      }
    }

    return totalMoves;
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int[][] coins = new int[2 * N][2];

    for (int i = 0; i < 2 * N; i++) {
      coins[i][0] = scanner.nextInt();
      coins[i][1] = scanner.nextInt();
    }

    System.out.println(minMovesToTarget(N, coins));
    scanner.close();
  }
}

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