Editorial for Разпръскване на коня


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

Sample solutions:

CSharp

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Collections;

namespace HorseMovesInMatrix
{
    class Program
    {
        static void Main(string[] args)
        {
            int r = int.Parse(Console.ReadLine());
            int c = int.Parse(Console.ReadLine());
            int startingRow = int.Parse(Console.ReadLine());
            int startingCol = int.Parse(Console.ReadLine());
            int[,] matrix = FillMatrix(r, c, startingRow, startingCol);
            int targetCol = c / 2;
            for (int row = 0; row < r; row++)
            {
                Console.WriteLine(matrix[row, targetCol]);
            }
        }
        public static int[,] FillMatrix(int r, int c, int row, int col)
        {
            int[] rowMoves = { -2, -2, -1, -1, +1, +1, +2, +2 };
            int[] colMoves = { -1, +1, -2, +2, -2, +2, -1, +1 };

            int[,] matrix = new int[r, c];
            matrix[row, col] = 1;
            Queue q = new Queue();
            q.Enqueue(new Coordinates(row, col));
            r--;
            c--;
            while (q.Count > 0)
            {
                Coordinates nextCoordinates = (Coordinates)q.Dequeue();
                row = nextCoordinates.Row;
                col = nextCoordinates.Col;
                for (int move = 0; move < rowMoves.Length; move++)
                {
                    int nextRow = row + rowMoves[move];
                    int nextCol = col + colMoves[move];
                    if (nextRow < 0 || nextRow > r || nextCol < 0 || nextCol > c)
                    {
                        continue;
                    }
                    if (matrix[nextRow, nextCol] != 0)
                    {
                        continue;
                    }
                    q.Enqueue(new Coordinates(nextRow, nextCol));
                    matrix[nextRow, nextCol] = matrix[row, col] + 1;
                }
            }
            return matrix;
        }
    }
    class Coordinates
    {
        private int row;
        private int col;
        public Coordinates(int row,int col) {
            this.row = row;
            this.col = col;
        }
        public int Row
        {
            get { return this.row; }
            set { row = value; }
        }
        public int Col
        {
            get { return this.col; }
            set { col = value; }
        }
    }
}

Java

public class Main {

    private static int[] horsePathRows = {2, 2, 1, 1, -1, -1, -2, -2};
    private static int[] horsePathCols = {-1, 1, 2, -2, -2, 2, -1, 1};
    private static boolean[][] isVisited;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int m = Integer.parseInt(bf.readLine());
        int r = Integer.parseInt(bf.readLine());
        int c = Integer.parseInt(bf.readLine());

        int[][] matrix = new int[n][m];
        matrix[r][c] = 1;
        isVisited = new boolean[n][m];
        isVisited[r][c] = true;
        bfs(matrix, r, c);
        int colToBePrinted = m/2;
        for (int[] row : matrix) {
            System.out.println(row[colToBePrinted]);
        }

    }

    private static void bfs(int[][] matrix, int row, int col) {
        Queue<Integer[]> queue = new ArrayDeque<>();
        Integer[] position = {row, col};
        queue.offer(position);

        while (!queue.isEmpty()) {
            Integer[] currentPosition = queue.poll();
            row = currentPosition[0];
            col = currentPosition[1];

            for (int i = 0; i < horsePathRows.length; i++) {
                int currRow = row + horsePathRows[i];
                int currCol = col + horsePathCols[i];

                if (currRow < 0 || currRow >= matrix.length || currCol < 0 || currCol >= matrix[0].length ||
                        isVisited[currRow][currCol]) {
                    continue;
                }


                Integer[] newPosition = {currRow, currCol};
                queue.offer(newPosition);
                matrix[currRow][currCol] = matrix[row][col] + 1;
                isVisited[currRow][currCol] = true;
            }

        }
    }
}

Comments

There are no comments at the moment.