#!/usr/bin/perl -w
# 從命令列上讀入棋盤的列數與行數, 讓騎士從第 0 列, 第 0 行開始走起,
# 看看是否可以一步一格, 把整個棋盤走完, 既不重複也不遺漏.
# http://www.cyut.edu.tw/~ckhung/b/pl/

use strict;
require "sitio";

my (%bdinfo, $board, $delta, $success);	#, 重要的全域變數
# Perl 內沒有真正的二維陣列, 我們用陣列的陣列來模擬二維陣列.
# $board->[0][3] 記載的是: 第 0 列第 3 行那一格是第幾步走到的?
# 請見詳談變數單元

$bdinfo{height} = $#ARGV >= 0 ? $ARGV[0] : 5;
$bdinfo{width} = $#ARGV >= 1 ? $ARGV[1] : 5;

# 請注意: 陣列的陣列在設定初始值時, 內層的括弧是方括弧!
$delta = [
	[2, 1],		[1, 2],		[-1, 2],	[-2, 1],
	[-2, -1],	[-1, -2],	[1, -2],	[2, -1],
];

$| = 1;
clearscr();

$board->[0][0] = 1;
drawcell(0, 0);
$success = march(2, 0, 0);

gotorc(23, 1);
printf($success ? "走完全程了!\n" : "這是不可能的任務!\n");

sub march {
    my ($step, $row, $col) = @_;
    my ($i, $r_next, $c_next);

    return 1 if ($step > $bdinfo{width} * $bdinfo{height});
    for ($i=0; $i<8; ++$i) {
	$r_next = $row + $delta->[$i][0];
	$c_next = $col + $delta->[$i][1];
	next if ($r_next < 0 or $r_next >= $bdinfo{height} or
	    $c_next < 0 or $c_next >= $bdinfo{width} or
	    defined $board->[$r_next][$c_next]);
	$board->[$r_next][$c_next] = $step;
	drawcell($r_next, $c_next);
	return 1 if (march($step+1, $r_next, $c_next));
	undef $board->[$r_next][$c_next];
	drawcell($r_next, $c_next);
    }
    return 0;
}

sub drawcell {
    my ($row, $col) = @_;
    my ($r0, $c0) = ((24 - $bdinfo{height}*2) / 2, (80 - $bdinfo{width}*4) / 2);

    gotorc($row*2+$r0, $col*4+$c0);
    printf "%2s", (defined $board->[$row][$col]) ? $board->[$row][$col] : "";
}