Guest User

Untitled

a guest
Jan 23rd, 2018
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.15 KB | None | 0 0
  1. import java.util.*;
  2.  
  3. public class E {
  4.     public static void main(String[] args) {
  5.         Scanner scan = new Scanner(System.in);
  6.         int numCases = scan.nextInt();
  7.         for (int z = 0; z < numCases; z++) {
  8.             int numBases = scan.nextInt();
  9.             int x = scan.nextInt();
  10.             int y = scan.nextInt();
  11.             int startx = scan.nextInt();
  12.             int starty = scan.nextInt();
  13.             int endx = scan.nextInt();
  14.             int endy = scan.nextInt();
  15.             int[][] enemyBases = new int[numBases][2];
  16.             int[][] map = new int[y][x];
  17.             LinkedList<Point> queue = new LinkedList<Point>();
  18.             for (int i = 0; i < numBases; i++) {
  19.                 enemyBases[i][0] = scan.nextInt();
  20.                 enemyBases[i][1] = scan.nextInt();
  21.                 map[enemyBases[i][1]][enemyBases[i][0]] = -1;
  22.                 queue.add(new Point(enemyBases[i][0],enemyBases[i][1]));
  23.             }
  24.             int[] dx = { 0, 1, 0, -1 };
  25.             int[] dy = { 1, 0, -1, 0 };
  26.             while (!queue.isEmpty()) {
  27.                 Point p = queue.removeFirst();
  28.                 int curx = p.x;
  29.                 int cury = p.y;
  30.                 for (int i = 0; i < 4; i++) {
  31.                     if ( curx + dx[i] >= 0 && curx + dx[i] < x && cury + dy[i] >= 0 && cury + dy[i] < y ) {
  32.                         if (map[cury][curx] == -1 && map[cury + dy[i]][curx + dx[i]] == 0) {
  33.                             map[cury + dy[i]][curx + dx[i]] = 1;
  34.                             queue.addLast(new Point(curx + dx[i],cury + dy[i]));
  35.                         }
  36.                         else if ( map[cury + dy[i]][curx + dx[i]] == 0 ){
  37.                             map[cury + dy[i]][curx + dx[i]] = map[cury][curx] + 1;
  38.                             queue.addLast(new Point(curx + dx[i],cury + dy[i]));
  39.                         }
  40.                     }      
  41.                 }  
  42.             }
  43.             for (int i = 0; i < numBases; i++) {
  44.                 map[enemyBases[i][1]][enemyBases[i][0]] = 0;
  45.             }
  46.             System.out.println("Done filling");
  47.             for (int[] arr : map)
  48.                 System.out.println(Arrays.toString(arr));
  49.            
  50.             PriorityQueue<Move> pq = new PriorityQueue<Move>();
  51.             pq.add(new Move(startx, starty, map[startx][starty], 0));
  52.             Move end = null;
  53.            
  54.             while (!pq.isEmpty()) {
  55.                 Move m = pq.poll();
  56.                 int curx = m.x;
  57.                 int cury = m.y;
  58.                 System.out.println()
  59.                 if (curx == endx && cury == endy) {
  60.                     end = m;
  61.                     break;
  62.                 }
  63.                 for (int i = 0; i < 4; i++) {
  64.                     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) {
  65.                         pq.add(new Move(curx + dx[i], cury + dy[i],
  66.                             Math.min(m.closest,map[cury+dy[i]][curx + dx[i]]), m.distance + 1));
  67.                         map[cury+dy[i]][curx + dx[i]] = -1;
  68.                     }
  69.                 }  
  70.             }
  71.             System.out.println(end.closest + " " + end.distance);
  72.         }
  73.        
  74.     }
  75.    
  76.     private static class Point {
  77.         public int x;
  78.         public int y;
  79.         public Point(int x, int y){
  80.             this.x = x;
  81.             this.y = y;
  82.         }
  83.     }
  84.    
  85.     private static class Move implements Comparable<Move> {
  86.        
  87.         public int x;
  88.         public int y;
  89.         public int closest;
  90.         public int distance;
  91.        
  92.         public Move(int x, int y, int closest, int distance){
  93.             this.x = x;
  94.             this.y = y;
  95.             this.closest = closest;
  96.             this.distance = distance;
  97.         }
  98.        
  99.         public int compareTo( Move m ) {
  100.             if ( closest > m.closest )
  101.                 return -1;
  102.             else if ( closest < m.closest )
  103.                 return 1;
  104.             else {
  105.                 if ( distance < m.distance )
  106.                     return -1;
  107.                 else if ( distance > m.distance )
  108.                     return 1;
  109.                 else
  110.                     return 0;
  111.             }
  112.         }
  113.     }
  114. }
Add Comment
Please, Sign In to add comment