Submission #1147158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147158		lucianaft	Coin Collecting (JOI19_ho_t4)	Java	0 / 100	58 ms	11344 KiB

joi2019_ho_t4

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
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<Position> targets = new ArrayList<>();
    for (int x = 1; x <= N; x++) {
      targets.add(new Position(x, 1, 0));
      targets.add(new Position(x, 2, 0));
    }

    Arrays.sort(coins, Comparator.comparingInt(a -> a[0]));
    targets.sort(Comparator.comparingInt(a -> a.x));

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

    for (int i = 0; i < 2 * N; i++) {
      int minDist = Integer.MAX_VALUE;
      int bestTarget = -1;
      for (int j = 0; j < targets.size(); j++) {
        if (!usedTarget[j]) {
          int dist = bfs(coins[i][0], coins[i][1], targets.get(j).x, targets.get(j).y);
          if (dist < minDist) {
            minDist = dist;
            bestTarget = j;
          }
        }
      }

      if (bestTarget != -1) {
        usedTarget[bestTarget] = true;
        totalMoves += minDist;
      }
    }

    return totalMoves;
  }

  private static int bfs(int startX, int startY, int targetX, int targetY) {
    if (startX == targetX && startY == targetY) return 0;

    Queue<Position> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();
    queue.add(new Position(startX, startY, 0));
    visited.add(startX + "," + startY);

    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    while (!queue.isEmpty()) {
      Position current = queue.poll();

      for (int[] dir : directions) {
        int newX = current.x + dir[0];
        int newY = current.y + dir[1];

        if (newX == targetX && newY == targetY) {
          return current.moves + 1;
        }

        String newState = newX + "," + newY;
        if (!visited.contains(newState)) {
          visited.add(newState);
          queue.add(new Position(newX, newY, current.moves + 1));
        }
      }
    }
    return Integer.MAX_VALUE;
  }

  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