2．逻辑游戏

题目描述:

一个同学给了我一个逻辑游戏。他给了我图1，在这个图上，每一段边界都已经进行了编号。我的任务是在图中画一条连续的曲线，使得这条曲线穿过每一个边界一次且仅穿过一次，而且曲线的起点和终点都在这整个区域的外面。这条曲线是容许自交的。

对于图1，我的同学告诉我画出这样的一条曲线（图2）是不可能的，但是对于有的图形（比如图3），画出这样一条曲线是可行的。对于给定的一个图，我想知道是否可以画出满足要求的曲线。

输入:

输入的图形用一个n×n的矩阵表示的。矩阵的每一个单元里有一个0到255之间（包括0和255）的整数。处于同一个区域的单元里的数相同，相邻区域的数不同（但是不相邻的区域里的数可能相同）。

输入的第一行是n（0<n<100）。以下的n行每行包括n个整数，分别给出对应的单元里的整数（这n个整数之间用空格分开）。图4给出了输入样例对应的图形。

输出:

    当可以画出满足题意的曲线的时候，输出“YES”；否则，输出“NO”。

输入样例:

3

1 1 2

1 2 2

1 1 2

输出样例:

    YES

程序：

program program2;

const

    d: array[0..7] of integer = (1, 0, -1, 0, 0, 1,   ①  );

var

    orig, n, i, j, ns: integer;

    a: array[0..101, 0..101] of integer;

    bun: boolean;

procedure plimba(x, y: integer);

var i, x1, y1: integer;

begin

    a[x, y] := -a[x, y];

    if (abs(a[x - 1, y]) <> orig) and ((  ②   <> a[x - 1, y])

or (abs(a[x, y - 1]) <> orig)) then inc(ns);

    if (abs(a[x + 1, y]) <> orig) and ((a[x + 1, y - 1] <> a[x + 1,y])

or (abs(a[x, y - 1]) <> orig)) then inc(ns);

    if (abs(a[x, y - 1]) <> orig) and ((  ③   <> a[x, y - 1])

or (abs(a[x - 1, y]) <> orig)) then inc(ns);

    if (abs(a[x, y + 1]) <> orig) and ((a[x - 1, y + 1] <> a[x,y + 1])

or (abs(a[x - 1, y]) <> orig)) then inc(ns);

    for i := 0 to 3 do begin

       x1 := x + d[2 * i];y1:=y+  ④  ;

       if (x1 >= 1) and (x1 <= n) and (y1 >= 1) and (y1 <= n) and

(  ⑤  ) then plimba(x1, y1);

    end;

end;

begin

    bun := true;

    read(n);

    for i := 0 to n+1 do

for j := 0 to n+1 do a[i, j] := 0;

    a[0, 0] := -1; a[n + 1, 0] := -1;

    a[0, n + 1] := -1; a[n + 1, n + 1] := -1;

    for i := 1 to n do

for j := 1 to n do read(a[i, j]);

    for i := 1 to n do

for j := 1 to n do

if a[i, j] > -1 then begin

              ns := 0;   ⑥  ;

              plimba(i, j);

              if ns mod 2 = 1 then bun := false;

            end;

    if bun then writeln('YES');

    if not bun then writeln('NO');

end.