首页 > 试题广场 >

逻辑游戏 题目描述: 一个同学给了我一个逻辑游戏。他给了我图

[填空题]
逻辑游戏
题目描述:
一个同学给了我一个逻辑游戏。他给了我图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, x1, y1;
    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++) {
        x1 = x + d[2 * i];
        y1 = y +   4;
        if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= n &&   5  )
        plimba(x1, y1);
    }
}
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;
}

这题的第一小问很明显有问题,应该是0,-1
发表于 2019-10-16 18:59:29 回复(0)