import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; public class Knight { /* Dimension of the board */ private static int n; /* Number of moves allowed */ private static int m; /* Position of the knight on the board */ private static int kX, kY; /* Position of the Queen on the board */ private static int qX, qY; /* Offsets for 8 possible moves of the knight */ private static byte[][] dirs = { {1,-2}, {2,-1}, {2,1}, {1,2}, {-1,2}, {-2,1}, {-2,-1}, {-1,-2} }; /* * Check whether position p falls on the board */ private static boolean onBoard(Position p) { return 0 <= p.x && p.x < n && 0 <= p.y && p.y < n; } /* * Generates a set of positions reachable from position start * within k moves. */ private static Set genPositions(Position start, int k) { Queue q = new LinkedList(); q.add(start); Set res = new TreeSet(); res.add(start); while(!q.isEmpty()) { Position p = q.remove(); Position next = new Position(p); next.l++; if (next.l > k) continue; for(int i = 0; i < 8; i++) { next.x += dirs[i][0]; next.y += dirs[i][1]; if (onBoard(next) && !(res.contains(next))) { Position np = new Position(next); q.add(np); res.add(np); } next.x -= dirs[i][0]; next.y -= dirs[i][1]; } } return res; } /* * Checks whether the Queen is reachable by the * Knight within m moves. */ private static boolean reachable() { Set s1 = genPositions(new Position(kX-1,kY-1,0), m/2); Set s2 = genPositions(new Position(qX-1,qY-1,0), m/2 + m%2); s1.retainAll(s2); if (s1.isEmpty()) { return false; } else { return true; } } public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); kX = sc.nextInt(); kY = sc.nextInt(); qX = sc.nextInt(); qY = sc.nextInt(); if (reachable()) { System.out.println("Knight can reach Queen within " + m + " moves!"); } else { System.out.println("Knight cannot reach Queen within " + m + " moves!"); } } }