import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Queue; /** * * @author tym3 */ public class Security { static int[][] D = { {-1, +1}, { 0, +1}, {+1, +1}, {-1, 0}, {+1, 0}, {-1, -1}, { 0, -1}, {+1, -1}, }; static class P { int x, y; P(int x, int y) { this.x = x; this.y = y; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] f = br.readLine().split(" "); int nGuards = Integer.parseInt(f[0]); int nIncidents = Integer.parseInt(f[1]); List
guards = new ArrayList<>(nGuards); for (int i = 0; i < nGuards; ++i) { f = br.readLine().split(" "); guards.add(new P(Integer.parseInt(f[0]), Integer.parseInt(f[1]))); } List
incidents = new ArrayList<>(nIncidents); for (int i = 0; i < nIncidents; ++i) { f = br.readLine().split(" "); incidents.add(new P(Integer.parseInt(f[0]), Integer.parseInt(f[1]))); } short[][] df = new short[5001][5001]; for (short[] row: df) { Arrays.fill(row, Short.MAX_VALUE); } List
guards2 = new ArrayList<>(nGuards); for (P g: guards) { if (df[g.x][g.y] != 0) { df[g.x][g.y] = 0; guards2.add(g); } } guards = guards2; // without duplicities Queue
q = new ArrayDeque<>(); q.addAll(guards2); while (!q.isEmpty()) { P p = q.remove(); for (int[] d: D) { int x2 = p.x + d[0]; int y2 = p.y + d[1]; if (x2 >= 0 && y2 >= 0 && x2 <= 5000 && y2 <= 5000 && df[x2][y2] == Short.MAX_VALUE) { // can visit neighbor q.add(new P(x2, y2)); df[x2][y2] = (short)(df[p.x][p.y] + 1); } } } PrintWriter pw = new PrintWriter(System.out); for (P inc: incidents) { pw.println(df[inc.x][inc.y]); } pw.flush(); } }