Cerinta completa

is a chess piece that moves in an L shape. We define the possible moves of as any movement from some position to some satisfying either of the following:

  • and , or
  • and

Note that and allow for the same exact set of movements. For example, the diagram below depicts the possible locations that or can move to from its current location at the center of a chessboard:

image

Observe that for each possible movement, the Knight moves units in one direction (i.e., horizontal or vertical) and unit in the perpendicular direction.

Given the value of for an chessboard, answer the following question for each pair where :

  • What is the minimum number of moves it takes for to get from position to position ? If it’s not possible for the Knight to reach that destination, the answer is -1 instead.

Then print the answer for each according to the Output Format specified below.

Input Format

A single integer denoting .

Constraints

Output Format

Print exactly lines of output in which each line (where ) contains space-separated integers describing the minimum number of moves must make for each respective (where ). If some cannot reach position , print -1 instead.

For example, if , we organize the answers for all the pairs in our output like this:

(1,1) (1,2)
(2,1) (2,2)

Sample Input 0

5

Sample Output 0

4 4 2 8
4 2 4 4
2 4 -1 -1
8 4 -1 1

Explanation 0

The diagram below depicts possible minimal paths for , , and :

image

One minimal path for is:

We then print 4 4 2 8 as our first line of output because took moves, took moves, took moves, and took moves.

In some of the later rows of output, it’s impossible for to reach position . For example, can only move back and forth between and so it will never reach .

Limbajul de programare folosit: python3

Cod:

#!/usr/bin/env python3

import queue

class Cell:
    def __init__(self, x, y, dist):
        self.x = x
        self.y = y
        self.dist = dist

def point_is_valid(horse, size):
    if any(x < 1 for x in horse) or any(x > size for x in horse):
        return False
    else:
        return True

def print_path(init, parent):
    tup = (init[0], init[1])
    if tup in parent.keys():
        prev = parent[tup]
        print_path((prev[0], prev[1]), parent)
    print(tup, end=' ')


def find_path_dijkstra(horse, king, size, a, b):
    res_dist = -1
    next_to_visit = {(horse[0], horse[1]):0}
    distances = [[-1] * (size + 1) for _ in range(size + 1)]
    distances[horse[0]][horse[1]] = 0
    parent = {}
    directions = [[a, b], [b, a], [a, -b], [b, -a], [-a, b], [-b, a], [-a, -b], [-b, -a]]
    #print("solving for: ({}, {})".format(a, b))

    while bool(next_to_visit):
        c = min(next_to_visit, key=next_to_visit.get)
        del next_to_visit[c]

        if c[0] == king[0] and c[1] == king[1]:
            res_dist = distances[c[0]][c[1]]
            break

        for di in directions:
            # child
            x, y = c[0] + di[0], c[1] + di[1]

            if point_is_valid([x, y], size) and distances[x][y] == -1:
                temp_path = distances[c[0]][c[1]] + 1
                if distances[x][y] == -1 or distances[x][y] > temp_path:
                    distances[x][y] = temp_path
                    next_to_visit[(x, y)] = temp_path
                    parent[(x, y)] = [c[0], c[1]]

    #for i in range(1, size + 1):
    #    print(" ".join(map(str, distances[i][1:])))

    #print_path(king, parent)
    #print()

    return res_dist

if __name__ == "__main__":
    board_size = int(input().strip())
    horse = [1, 1]
    king = [board_size, board_size]

    for a in range(1, board_size):
        for b in range(1, board_size):
            print("{}".format(find_path_dijkstra(horse, king, board_size, a, b)), end = ' ')
        print()

Scor obtinut: 1.0

Submission ID: 464604121

Link challenge: https://www.hackerrank.com/challenges/knightl-on-chessboard/problem

KnightL on a Chessboard