다각형그리기

다각형그리기

모눈종이에 다각형을 그리려고 한다. 그리는 방법은 모양수열로 표시된다. 모양수열은 1과 4사이의 숫자가 연속되어 나열된 것으로 1은 오른쪽으로, 2는 위쪽으로, 3은 왼쪽으로, 4는 아래쪽으로 한 칸씩 그리는 것을 말한다.

 

예를 들어 아래 그림의 다각형 (2)는 점 A에서 시작하여 화살표 방향으로 모양수열 1411433322를 따라서 그린 것이다. 다각형 (3)은 점 B에서 시작하여 화살표 방향으로 모양수열 3221411433을 따라서 그린 것이다. 또한 다각형(4)는 점 C에서 시작하여 화살표 방향으로 모양수열 4411123323을 따라서 그린 것이다. 다각형 (2), (3), (4)는 다각형 (1)과 같으므로 모양수열들 1411433322, 3221411433, 4411123323은 모두 같은 다각형을 그릴 수 있다. 단, 다각형이 회전된 것이나 뒤집어진 것은 같은 다각형이 아니다. 그러므로 아래 그림의 다각형 (5)와 (6)은 다각형 (1)과 다르다.

 

 

 

한 개의 표본 모양수열과 여러 모양수열들이 주어졌을 때 표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열들을 모두 찾는 프로그램을 작성하시오.

 

입력형식

첫째 줄에는 표본 모양수열의 길이(숫자의 개수)가 주어지고, 둘째 줄에는 표본 모양수열이 주어진다. 셋째 줄에는 모양수열의 개수가 주어지고 넷째 줄부터는 각 줄에 표본 모양수열과 같은 길이의 모양수열이 하나씩 주어진다. 단, 모양수열들의 개수는 최대 100 개이고 모양수열의 길이는 최대 50 이다. 모양수열의 각 숫자 사이에는 빈칸이 하나 있다.

 

출력형식

첫째 줄에는 입력된 표본 모양수열과 같은 다각형을 그리는 모양수열들의 개수를 출력한다. 둘째 줄부터는 각 줄에 표본 모양수열과 같은 다각형을 그릴 수 있는 모양수열을 출력한다. 출력되는 모양수열의 숫자들은 한 칸 띄고 출력한다.

 

입력 예	출력 예
10 1 4 1 1 4 3 3 3 2 2 3 3 2 2 1 4 1 1 4 3 3 1 4 4 3 3 3 2 1 1 2 4 4 1 1 1 2 3 3 2 3	2 3 2 2 1 4 1 1 4 3 3 4 4 1 1 1 2 3 3 2 3

 

소스코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>

int a[50], b[100][50], c[100], d[50];
int n, m, ret;

int match() {
    int i, j;
    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (a[j] != d[(i + j) % n])
                break;
        }

        if (j == n)
            return 1;
    }

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n; j++)
        {
            if (a[n-1-j] != d[(i + j) % n])
                break;
        }

        if (j == n)
            return 1;
    }

    return 0;
}

int main() 
{
    int i, j;

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

    scanf("%d", &m);
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
            scanf("%d", &b[i][j]);

        for (j = 0; j < n; j++)
            d[j] = b[i][j];

        if (match())
            c[i] = 1;

        for (j = 0; j < n; j++)
        {
            if (d[j] == 1)
                d[j] = 3;
            else if (d[j] == 2)
                d[j] = 4;
            else if (d[j] == 3)
                d[j] = 1;
            else if (d[j] == 4)
                d[j] = 2;
        }
        if (match())
            c[i] = 1;

        if (c[i])
            ret++;
    }

    printf("%d\n", ret);
    for (i = 0; i < m; i++)
    {
        if (c[i])
        {
            for (j = 0; j < n; j++)
            {
                if (j)
                    printf(" ");

                printf("%d", b[i][j]);
            }
            printf("\n");
        }
    }

    return 0;
}