Editorial for Horse Path


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: doncho

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];

    int[] dRows = {-2, -2, -1, -1, +1, +1, +2, +2};
    int[] dCols = {-1, +1, -2, +2, -2, +2, -1, +1};

    int counter = 1;

    for (int r = 0; r < matrix.length; r++) {
      for (int c = 0; c < matrix[r].length; c++) {
        int row = r;
        int col = c;

        while (matrix[row][col] == 0) {
          matrix[row][col] = counter;
          counter++;

          for (int dir = 0; dir < dRows.length; dir++) {
            int nextRow = row + dRows[dir];
            int nextCol = col + dCols[dir];

            if (nextRow < 0 || nextRow >= matrix.length ||
              nextCol < 0 || nextCol >= matrix.length) {
              continue;
            }

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

            row = nextRow;
            col = nextCol;
            break;
          }
        }
      }
    }

    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.