CSES - Knight's Tour | Hành trình của quân mã

Tác giả:

Flower_On_Stone , nhphucqt , NguyễnAnhQuốc_83

Dạng bài

Điểm: 2200 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Với vị trí xuất phát của một quân mã trên bàn cờ \(8 \times 8\), nhiệm vụ của bạn là tìm một chuỗi các nước đi sao cho nó truy cập đúng một lần vào mỗi ô vuông.

Trong mỗi lần di chuyển, quân mã có thể di chuyển hai bước theo chiều ngang và một bước theo chiều dọc, hoặc một bước theo chiều ngang và hai bước theo chiều dọc.

Input

Dòng duy nhất là hai số nguyên \(x\) và \(y\): vị trí xuất phát của quân mã.

Output

In một lưới hiển thị cách di chuyển của quân mã (theo ví dụ). Bạn có thể in bất kỳ giải pháp hợp lệ nào.

Constraints

\(1 \leq x, y \leq 8\)

Example

Test 1

Input

2 1

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

Bình luận

-1

rock 7:09 p.m. 23 Tháng 10, 2024

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)

6 bình luận nữa