逻辑游戏

题目描述:

一个同学给了我一个逻辑游戏。他给了我图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

程序：

#include <stdio.h>


#include <math.h>


int orig, n, ns, a [102][102], bun;


int d[]= {1,0,-1,0,0,1,___(1)___};


void plimba(int x, int y) {


	int i,xx, yy;


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


	if(abs(a[x-1][y]) !=orig&&( ___(2)___  !=a[x-1][y]||abs(a[x][y-1]) !=orig))	ns++;


	if(abs(a[x+1][y]) !=orig&& (a[x+1][y-1]!=a[x+1][y]||abs(a[x][y-1]) !=orig))	ns++;


	if(abs(a[x][y-1]) !=orig&&( ___(3)___  !=a[x][y-1]||abs(a[x-1][y]) !=orig))	ns++;


	if(abs(a[x][y+1]) !=orig&&(a[x-1][y+1] !=a[x][y+1]||abs(a[x-1][y]) !=orig))	ns++;


	for(i=0; i<4 ; i++) {


		xx=x+d[2*i]; yy=y+___(4)___;


		if(xx>=1&&xx<=n&&yy>=1&&yy<=n&& ___(5)___ )plimba(xx,yy);


	}


}


int main () {


	int i,j;


	bun=1;


	scanf("%d",&n);


	for (i=0; i<=n+1; i++)


	for (j=0; j<=n+1; j++)	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; i<=n; i++)


	for (j=1; j<=n; j++) scanf("%d",&a[i][j]);


	for (i=1; i<=n ; i++)


		for(j=1; j<=n; j++) {


			if(a[i][j]>-1) {


				ns=0; ___(6)___;				


				plimba (i,j);


				if(ns%2==1) bun=0;


			}


		}


	if (bun)printf("YES\n");else printf("NO\n");


	return 0;


}

选择题