CSES - Knight's Tour | Hành trình của quân mã
View as PDF
Points:
2200 (p)
Time limit:
1.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Given a starting position of a knight on an \(8 \times 8\) chessboard, your task is to find a sequence of moves such that it visits every square exactly once.
On each move, the knight may either move two steps horizontally and one step vertically, or one step horizontally and two steps vertically.
Input
- The only line has two integers \(x\) and \(y\): the knight's starting position.
Output
- Print a grid that shows how the knight moves (according to the example). You can print any valid solution.
Constraints
- \(1 \leq x,y \leq 8\)
Example
Sample input
2 1
Sample output
8 1 10 13 6 3 20 17
11 14 7 2 19 16 23 4
26 9 12 15 24 5 18 21
49 58 25 28 51 22 33 30
40 27 50 59 32 29 52 35
57 48 41 44 37 34 31 62
42 39 46 55 60 63 36 53
47 56 43 38 45 54 61 64
Comments
const
N = 8;
var
board: array[1..N, 1..N] of integer;
xMove: array[1..8] of integer = (2, 1, -1, -2, -2, -1, 1, 2);
yMove: array[1..8] of integer = (1, 2, 2, 1, -1, -2, -2, -1);
i, j: integer;
procedure printSolution;
var
x, y: integer;
begin
for x := 1 to N do
begin
for y := 1 to N do
write(board[x, y]:3, ' ');
writeln;
end;
end;
function isSafe(x, y: integer): boolean;
begin
isSafe := (x >= 1) and (x <= N) and (y >= 1) and (y <= N) and (board[x, y] = 0);
end;
function getDegree(x, y: integer): integer;
var
count, k, nextX, nextY: integer;
begin
count := 0;
for k := 1 to 8 do
begin
nextX := x + xMove[k];
nextY := y + yMove[k];
if isSafe(nextX, nextY) then
count := count + 1;
end;
getDegree := count;
end;
function solveKTUtil(x, y, movei: integer): boolean;
var
k, minDegree, nextX, nextY, bestX, bestY, degree: integer;
begin
if movei = N * N + 1 then
exit(True);
minDegree := 9;
bestX := -1;
bestY := -1;
for k := 1 to 8 do
begin
nextX := x + xMove[k];
nextY := y + yMove[k];
if isSafe(nextX, nextY) then
begin
degree := getDegree(nextX, nextY);
if degree < minDegree then
begin
minDegree := degree;
bestX := nextX;
bestY := nextY;
end;
end;
end;
if bestX <> -1 then
begin
board[bestX, bestY] := movei;
if solveKTUtil(bestX, bestY, movei + 1) then
exit(True)
else
board[bestX, bestY] := 0;
end;
exit(False);
end;
procedure solveKT(xStart, yStart: integer);
begin
for i := 1 to N do
for j := 1 to N do
board[i, j] := 0;
board[xStart, yStart] := 1;
if not solveKTUtil(xStart, yStart, 2) then
writeln('Me may beo haha dung la mot con ga')
else
printSolution;
end;
var
xStart, yStart: integer;
begin
readln(xStart, yStart);
solveKT(xStart, yStart);
end.
Sai chỗ nào mà tui dc có 500/2200 vậy(pascal)
Tui thích chơi cờ vua nhưng làm bài này khó quá ;-;
hint: hãy đi mã ở ô có ít bước tiếp đi tiếp theo nhất
độ phức tạp: O(8*8)?
bài này quay lui dc ko ta 🙂
https://ideone.com/tVF0Cs
cuối cùng đã giải được bằng python sau 61 dòng :((
admin có thể xem qua code và giúp e được k ạ, luôn bị bị time 2 test @@