The minimum number of moves for which two knights will meet

Question

On a chessboard consisting of M rows and N columns (for example, 8x10), there are two knights, the user enters their coordinates himself (for example, (2, 4) is a white knight and (7, 9) is a black knight). Each knight is located in the it's cell, but it is possible that both knights are in the same cell. The knights take turns making moves in accordance with the rules of the chess knight's movement (the white knight goes first). The goal of the game is to place both horses in the same cell as quickly as possible.

Input format

The first line of the file contains the values M and N (2≤M,N≤1000). The second and third lines contain the coordinates of the cells in which the white and black knight are located, respectively. The first coordinate is in the range from 1 to M, the second is in the range from 1 to N.

Output format

Print a single number — the number of moves required to complete the game. If the knights can never be placed in the same square, print -1.

Since I'm new to algorithms and data structures, I tried to solve this problem like this: run for loop on all 64 possible combinations of two moves of a white and black knight, make a move for each knight (checking if it goes beyond the scope), check if there is a match and, if there is, then output it. Then run the same cycle inside of the current. At the same time, the moves are counted and it is also output. However, I have encountered such a problem that I cannot automate the process of running this loop inside the loop, I cannot know the number of times that this loop needs to be run. I tried to create a function with recursion in which it was possible to call this loop if a match has not yet been found, but I failed. I decided that it would not work that way to solve this problem, so I looked at the algorithms that are usually used in such tasks. I was thinking of somehow creating an adjacency list for two horses, where the vertices are all the calculated positions of the horse; use BFS, or the Dijkstra algorithm.

Solved. Here is my swift code:

import Foundation

let mnstr = readLine()?.components(separatedBy: " ")

let m = Int(mnstr![0])!
let n = Int(mnstr![1])!

let wstr = readLine()?.components(separatedBy: " ")
let bstr = readLine()?.components(separatedBy: " ")

var w: [Int] = []
var b: [Int] = []
var count: Int = 0
let moves: [[Int]] = [[2, -1], [1, 2], [-2, -1], [1, -2], [2, 1], [-1, 2], [-2, 1], [-1, -2]]

w.append(Int(wstr![0])!)
w.append(Int(wstr![1])!)
b.append(Int(bstr![0])!)
b.append(Int(bstr![1])!)

var wp: Set = [w]
var bp: Set = [b]

func oneMove(lst: Set<[Int]>) -> Set<[Int]>{
    let curr = lst
    var out = lst
    for i in curr {
        for move in moves {
            let item = [i[0] + move[0], i[1] + move[1]]
            if item[0] < 1 || item[0] > m || item[1] < 1 || item[1] > n {
                continue
            }
            out.insert(item)
        }
    }
    return out
}

while bp.intersection(wp).isEmpty == true {
    wp = oneMove(lst: wp)
    count += 1
    if wp.intersection(bp).isEmpty != true {
        break
    }
    bp = oneMove(lst: bp)
    count += 1
    if wp.intersection(bp).isEmpty != true {
        break
    }
    if wp.count == 1 || bp.count == 1 {
        count = -1
        break
    }
}

print(count)

Scott Hunter · Accepted Answer

This would seem to be the basic logic you want, where ?_locs is a set of the locations a particular knight can be in (initialized to its initial location) and one_move yields a set of the locations that can be reached in 1 move from one of the locations in the argument:

while bk_locs intersect wh_locs is empty:
    bk_locs = one_move(bk_locs)
    wh_locs = one_move(wh_locs)

What this doesn't handle is counting moves (trivial) or identifying when to give up (harder).

The minimum number of moves for which two knights will meet

Answers (2)

Related Questions