11.2.2(final)

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

/**
 * Created by Сергей on 20.05.2016.
 */

public class Solution {
    public static void main(String args[]) {
        //задача поиск кратчайшего пути  для этого используем алгоритм поиска в ширину
        //как только находим путь, поиск закончен
        int n; // размер доски
        int x1, x2, y1, y2; // координаты начала и конца
        int x, y, dist;
        int wayDist = 0;
        Pair point;

        //ввод
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        x1 = sc.nextInt();
        y1 = sc.nextInt();
        x2 = sc.nextInt();
        y2 = sc.nextInt();


        ArrayDeque<Pair> q = new ArrayDeque<Pair>();//здесь храним порядок обхода доски
        int matrix[][] = new int[n][n];// шахматное поле, будем помечать пройденные точки 1, не пройденные 0
        int d[][] = new int[n][n]; // ходов до точки

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                d[i][j] = -1;

        d[x1 - 1][y1 - 1] = 0;
        matrix[x1 - 1][y1 - 1] = 1;
        q.offer(new Pair(x1, y1));

        // поиск пути BFS
        while (!q.isEmpty()) {
            point = q.poll();
            x = point.getX();
            y = point.getY();
            dist = d[x - 1][y - 1];
            if (x == x2 && y == y2)
                wayDist = dist;


            if (x + 2 <= n) {
                if (y - 1 >= 1)
                    if (matrix[x + 2 - 1][y - 1 - 1] == 0) {
                        q.offer(new Pair(x + 2, y - 1));//добавить в очередь
                        matrix[x + 2 - 1][y - 1 - 1] = 1;// пометка на матрице
                        d[x + 2 - 1][y - 1 - 1] = dist + 1;// пометить в массиве расстояний
                    }
                if (y + 1 <= n)
                    if (matrix[x + 2 - 1][y + 1 - 1] == 0) {
                        q.offer(new Pair(x + 2, y + 1));
                        matrix[x + 2 - 1][y + 1 - 1] = 1;
                        d[x + 2 - 1][y + 1 - 1] = dist + 1;
                    }
            }
            if (x - 2 >= 1) {
                if (y - 1 >= 1)
                    if (matrix[x - 2 - 1][y - 1 - 1] == 0) {
                        q.offer(new Pair(x - 2, y - 1));
                        matrix[x - 2 - 1][y - 1 - 1] = 1;
                        d[x - 2 - 1][y - 1 - 1] = dist + 1;
                    }
                if (y + 1 <= n)
                    if (matrix[x - 2 - 1][y + 1 - 1] == 0) {
                        q.offer(new Pair(x - 2, y + 1));
                        matrix[x - 2 - 1][y + 1 - 1] = 1;
                        d[x - 2 - 1][y + 1 - 1] = dist + 1;
                    }
            }
            if (y + 2 <= n) {
                if (x - 1 >= 1)
                    if (matrix[x - 1 - 1][y + 2 - 1] == 0) {
                        q.offer(new Pair(x - 1, y + 2));
                        matrix[x - 1 - 1][y + 2 - 1] = 1;
                        d[x - 1 - 1][y + 2 - 1] = dist + 1;
                    }
                if (x + 1 <= n)
                    if (matrix[x + 1 - 1][y + 2 - 1] == 0) {
                        q.offer(new Pair(x + 1, y + 2));
                        matrix[x + 1 - 1][y + 2 - 1] = 1;
                        d[x + 1 - 1][y + 2 - 1] = dist + 1;
                    }
            }
            if (y - 2 >= 1) {
                if (x - 1 >= 1)
                    if (matrix[x - 1 - 1][y - 2 - 1] == 0) {
                        q.offer(new Pair(x - 1, y - 2));
                        matrix[x - 1 - 1][y - 2 - 1] = 1;
                        d[x - 1 - 1][y - 2 - 1] = dist + 1;
                    }
                if (x + 1 <= n)
                    if (matrix[x + 1 - 1][y - 2 - 1] == 0) {
                        matrix[x + 1 - 1][y - 2 - 1] = 1;
                        q.offer(new Pair(x + 1, y - 2));
                        d[x + 1 - 1][y - 2 - 1] = dist + 1;
                    }
            }
        }
        //вывести длинну пути , массив расстояний до точек
        System.out.println(wayDist);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++)
                System.out.print(d[i][j] + " ");
            System.out.println();
        }
        //раскрутка пути
        if (wayDist > 0) {
            Pair way[] = new Pair[wayDist];
            way[0] = new Pair(x2, y2);
            for (int i = 1; i < wayDist; i++) {
                x = way[i - 1].getX();
                y = way[i - 1].getY();
                if (x + 2 <= n) {
                    if (y - 1 >= 1)
                        if (d[x + 2 - 1][y - 1 - 1] == wayDist - i) {
                            way[i] = new Pair(x + 2, y - 1);
                            continue;
                        }
                    if (y + 1 <= n)
                        if (d[x + 2 - 1][y + 1 - 1] == wayDist-i ) {
                            way[i] = new Pair(x + 2, y + 1);
                            continue;
                        }
                }
                if (x - 2 >= 1) {
                    if (y - 1 >= 1)
                        if (d[x - 2 - 1][y - 1 - 1] == wayDist-i) {
                            way[i] = new Pair(x - 2, y - 1);
                            continue;
                        }
                    if (y + 1 <= n)    //здесь ошибка
                        if (d[x - 2 - 1][y + 1 - 1] == wayDist-i) {
                            way[i] = new Pair(x - 2, y + 1);
                            continue;
                        }
                }
                if (y + 2 <= n) {
                    if (x - 1 >= 1)
                        if (d[x - 1 - 1][y + 2 - 1] == wayDist-i) {
                            way[i] = new Pair(x - 1, y + 2);
                            continue;
                        }
                    if (x + 1 <= n)
                        if (d[x + 1 - 1][y + 2 - 1] == wayDist-i) {
                            way[i] = new Pair(x + 1, y + 2);
                            continue;
                        }
                }
                if (y - 2 >= 1) {
                    if (x - 1 >= 1)
                        if (d[x - 1 - 1][y - 2 - 1] == wayDist-i) {
                            way[i] = new Pair(x - 1, y - 2);
                            continue;
                        }
                    if (x + 1 <= n)
                        if (d[x + 1 - 1][y - 2 - 1] == wayDist-i) {
                            way[i] = new Pair(x + 1, y - 2);
                            continue;
                        }
                }
            }
            System.out.println(x1 + " " + y1);
            for (int i = wayDist - 1; i >= 0; i--) {
                System.out.println(way[i].getX() + " " + way[i].getY());
            }

        }
    }
}