Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- public class E {
- public static void main(String[] args) {
- Scanner scan = new Scanner(System.in);
- int numCases = scan.nextInt();
- for (int z = 0; z < numCases; z++) {
- int numBases = scan.nextInt();
- int x = scan.nextInt();
- int y = scan.nextInt();
- int startx = scan.nextInt();
- int starty = scan.nextInt();
- int endx = scan.nextInt();
- int endy = scan.nextInt();
- int[][] enemyBases = new int[numBases][2];
- int[][] map = new int[y][x];
- LinkedList<Point> queue = new LinkedList<Point>();
- for (int i = 0; i < numBases; i++) {
- enemyBases[i][0] = scan.nextInt();
- enemyBases[i][1] = scan.nextInt();
- map[enemyBases[i][1]][enemyBases[i][0]] = -1;
- queue.add(new Point(enemyBases[i][0],enemyBases[i][1]));
- }
- int[] dx = { 0, 1, 0, -1 };
- int[] dy = { 1, 0, -1, 0 };
- while (!queue.isEmpty()) {
- Point p = queue.removeFirst();
- int curx = p.x;
- int cury = p.y;
- for (int i = 0; i < 4; i++) {
- if ( curx + dx[i] >= 0 && curx + dx[i] < x && cury + dy[i] >= 0 && cury + dy[i] < y ) {
- if (map[cury][curx] == -1 && map[cury + dy[i]][curx + dx[i]] == 0) {
- map[cury + dy[i]][curx + dx[i]] = 1;
- queue.addLast(new Point(curx + dx[i],cury + dy[i]));
- }
- else if ( map[cury + dy[i]][curx + dx[i]] == 0 ){
- map[cury + dy[i]][curx + dx[i]] = map[cury][curx] + 1;
- queue.addLast(new Point(curx + dx[i],cury + dy[i]));
- }
- }
- }
- }
- for (int i = 0; i < numBases; i++) {
- map[enemyBases[i][1]][enemyBases[i][0]] = 0;
- }
- System.out.println("Done filling");
- for (int[] arr : map)
- System.out.println(Arrays.toString(arr));
- PriorityQueue<Move> pq = new PriorityQueue<Move>();
- pq.add(new Move(startx, starty, map[startx][starty], 0));
- Move end = null;
- while (!pq.isEmpty()) {
- Move m = pq.poll();
- int curx = m.x;
- int cury = m.y;
- System.out.println()
- if (curx == endx && cury == endy) {
- end = m;
- break;
- }
- for (int i = 0; i < 4; i++) {
- if ( curx + dx[i] >= 0 && curx + dx[i] < x && cury + dy[i] >= 0 && cury + dy[i] < y && map[cury + dy[i]][curx + dx[i]] != -1) {
- pq.add(new Move(curx + dx[i], cury + dy[i],
- Math.min(m.closest,map[cury+dy[i]][curx + dx[i]]), m.distance + 1));
- map[cury+dy[i]][curx + dx[i]] = -1;
- }
- }
- }
- System.out.println(end.closest + " " + end.distance);
- }
- }
- private static class Point {
- public int x;
- public int y;
- public Point(int x, int y){
- this.x = x;
- this.y = y;
- }
- }
- private static class Move implements Comparable<Move> {
- public int x;
- public int y;
- public int closest;
- public int distance;
- public Move(int x, int y, int closest, int distance){
- this.x = x;
- this.y = y;
- this.closest = closest;
- this.distance = distance;
- }
- public int compareTo( Move m ) {
- if ( closest > m.closest )
- return -1;
- else if ( closest < m.closest )
- return 1;
- else {
- if ( distance < m.distance )
- return -1;
- else if ( distance > m.distance )
- return 1;
- else
- return 0;
- }
- }
- }
- }
Add Comment
Please, Sign In to add comment