/* * To change this license header, choose License Headers in Project Properties. * To change this template file, choose Tools | Templates * and open the template in the editor. */ package security; import java.util.ArrayList; import java.util.Scanner; /** * * @author boban3 */ // 0 volne, 1 Guard, 2 incedent, 3 Uzsombol public class Security { /** * @param args the command line arguments */ public static void main(String[] args) { Scanner vstup = new Scanner(System.in); int[][] pole = new int[5000][5000]; int pocetG = vstup.nextInt(); int pocetI = vstup.nextInt(); for(int i = 0; i < pocetG;i++){ int guardX = vstup.nextInt(); int guardY = vstup.nextInt(); pole[guardX][guardY] = 1; } int[] incidentyX = new int[pocetI]; int[] incidentyY= new int[pocetI]; for(int i = 0; i < pocetI;i++){ int incidentX = vstup.nextInt(); int incidentY = vstup.nextInt(); incidentyX[i] = incidentX; incidentyY[i] = incidentY; // pole[incidentX][incidentY] = ; } //vytvor kopiju int[][] poleK = new int[5000][5000]; for (int a = 0; a < 5000; a++) { for (int b = 0; b < 5000; b++) { poleK[a][b] = pole[a][b]; } } ArrayList epsi = new ArrayList<>(); for(int i = 0; i < pocetI;i++){ int pocetKrokov = 0; Bod prvy = new Bod(incidentyX[i],incidentyY[i]); if(pole[prvy.x][prvy.y] == 1){ System.out.println(pocetKrokov); }else{ epsi.clear(); epsi.add(prvy); ArrayList temp = new ArrayList<>(); pocetKrokov++; while(true){ if (epsi.isEmpty()) { epsi = (ArrayList) temp.clone(); temp.clear(); pocetKrokov++; } Bod aktualny = epsi.get(0); epsi.remove(0); if((aktualny.y + 1) < 5000 && (aktualny.x + 1) < 5000) if(pole[aktualny.x + 1][aktualny.y + 1] == 1){ // vpravo hore break; }else{ if(pole[aktualny.x + 1][aktualny.y + 1] == 0){ pole[aktualny.x + 1][aktualny.y + 1] = 3; temp.add(new Bod(aktualny.x + 1,aktualny.y + 1)); } } if((aktualny.x + 1) < 5000) if(pole[aktualny.x + 1][aktualny.y] == 1){ //vpravo break; }else{ if(pole[aktualny.x + 1][aktualny.y] == 0){ pole[aktualny.x + 1][aktualny.y] = 3; temp.add(new Bod(aktualny.x + 1,aktualny.y)); } } if((aktualny.y - 1) >= 0 && (aktualny.x + 1) < 5000) if(pole[aktualny.x + 1][aktualny.y - 1] == 1){ //vpravo dole break; }else{ if(pole[aktualny.x + 1][aktualny.y - 1] == 0){ pole[aktualny.x + 1][aktualny.y - 1] = 3; temp.add(new Bod(aktualny.x + 1,aktualny.y - 1)); } } if((aktualny.y - 1) >= 0) if(pole[aktualny.x][aktualny.y - 1] == 1){ //dole break; }else{ if(pole[aktualny.x][aktualny.y - 1] == 0){ pole[aktualny.x][aktualny.y - 1] = 3; temp.add(new Bod(aktualny.x,aktualny.y - 1)); } } if((aktualny.y - 1) >= 0 && (aktualny.x - 1) >= 0) if(pole[aktualny.x - 1][aktualny.y - 1] == 1){ //vlavo dole break; }else{ if(pole[aktualny.x - 1][aktualny.y - 1] == 0){ pole[aktualny.x - 1][aktualny.y - 1] = 3; temp.add(new Bod(aktualny.x - 1,aktualny.y - 1)); } } if((aktualny.x - 1) >= 0) if(pole[aktualny.x - 1][aktualny.y] == 1){ //vlavo break; }else{ if(pole[aktualny.x - 1][aktualny.y] == 0){ pole[aktualny.x - 1][aktualny.y] = 3; temp.add(new Bod(aktualny.x - 1,aktualny.y)); } } if((aktualny.y + 1) < 5000 && (aktualny.x - 1) >= 0) if(pole[aktualny.x - 1][aktualny.y + 1] == 1){ //vlavo hore break; }else{ if(pole[aktualny.x - 1][aktualny.y + 1] == 0){ pole[aktualny.x - 1][aktualny.y + 1] = 3; temp.add(new Bod(aktualny.x - 1,aktualny.y + 1)); } } if((aktualny.y + 1) < 5000) if(pole[aktualny.x][aktualny.y + 1] == 1){ //hore break; }else{ if(pole[aktualny.x][aktualny.y + 1] == 0){ pole[aktualny.x][aktualny.y + 1] = 3; temp.add(new Bod(aktualny.x,aktualny.y + 1)); } } } System.out.println(pocetKrokov); } for (int a = 0; a < 5000; a++) { for (int b = 0; b < 5000; b++) { pole[a][b] = poleK[a][b]; } } } } static class Bod{ public int x; public int y; public Bod(int x, int y) { this.x = x; this.y = y; } } }