Editorial for Knight Moves


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
by: donchominkov

Sample solutions:

Video in BG

JavaScript

const n = +gets();

let matrix = []
for (let i = 0; i < n; i++) {
    matrix.push([]);
}

const drows = [-2, -2, -1, -1, +1, +1, +2, +2];
const dcols = [-1, +1, -2, +2, -2, +2, -1, +1];
const dirsCounts = drows.length;

let count = 1;

for (let r = 0; r < n; r += 1) {
    for (let c = 0; c < n; c += 1) {
        if (matrix[r][c]) {
            continue;
        }

        let cellFound = true;
        let row = r;
        let col = c;

        while (cellFound) {
            cellFound = false;

            matrix[row][col] = count;
            count += 1;

            let direction = 0;
            while (direction < dirsCounts && !cellFound) {
                const nextRow = row + drows[direction];
                const nextCol = col + dcols[direction];
                direction += 1;
                if (nextRow < 0 || n <= nextRow) {
                    continue;
                }
                if (nextCol < 0 || n <= nextCol) {
                    continue;
                }

                if (matrix[nextRow][nextCol]) {
                    continue;
                }

                cellFound = true;
                row = nextRow;
                col = nextCol;
                break;

            }
        }
    }
}

for (const row of matrix) {
    print(row)
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[][] matrix = new int[n][n];

        // All possible horse moves (8) ordered by priority (top most, left most)
        int[] horseMovesHorizontal = {-2, -2, -1, -1, +1, +1, +2, +2};
        int[] horseMovesVertical = {-1, +1, -2, +2, -2, +2, -1, +1};

        int movesCounter = 1;
        // For each cell in the matrix that is not used try to make horse moves
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < n; c++) {
                int currentRow = r;
                int currentCol = c;

                // Make moves while cell is not visited
                while (matrix[currentRow][currentCol] == 0) {
                    matrix[currentRow][currentCol] = movesCounter;
                    movesCounter++;

                    // Search for possible move
                    for (int move = 0; move < horseMovesHorizontal.length; move++) {
                        int nextRow = currentRow + horseMovesHorizontal[move];
                        int nextCol = currentCol + horseMovesVertical[move];

                        // Check if move goes out of the matrix
                        if (nextRow < 0 || nextRow >= matrix.length ||
                                nextCol < 0 || nextCol >= matrix.length) {
                            continue;
                        }

                        // Check if the cell is visited
                        if (matrix[nextRow][nextCol] != 0) {
                            continue;
                        }

                        currentRow = nextRow;
                        currentCol = nextCol;
                        break;
                    }
                }
            }
        }

        // Print the output
        for (int[] row : matrix) {
            String result = "";
            for (int cell : row) {
                result += cell + " ";
            }
            System.out.println(result.trim());
        }
    }
}

Comments

There are no comments at the moment.