[BOJ 1331] 나이트투어

https://www.acmicpc.net/problem/1331

불러오는 중입니다...

---

이 문제를 풀기위해서는 3가지 조건을 만족시키면 된다.

1. 나이트의 이동방식처럼 움직였는지

2. 마지막 지점에서 처음 지점으로 갈 수 있는지

3. 모든 지점을 지났는지

 

사실 3번은 따로 코드로 짤 필요는 없다.

 

이 문제에서는 총 36줄로 움직이는 위치가 주어지고, 모든 위치가 겹치지 않는다면 모든 판을 지난 것이다.

 

1번은 바로 전의 위치와 현 위치의 차이가 나이트가 움직이는 방식인지 확인하면 된다.

 

즉, 알파벳 부분의 차의 절대값이 2일 때 숫자 부분의 차의 절대값이 1이거나, 이 반대의 경우 성립한다.

 

2번은 처음의 입력받은 것을 저장해뒀다가 마지막 위치와 비교하여 확인하면 된다. 

 

두 위치의 차가 나이트의 이동방식과 일치하는지 알아보면 된다.

---

#include <stdio.h>
 
 
int board[6][6];
 
int abs(int a)
{
    return a > 0 ? a : -a;
}
 
int CanMove(int x1, int y1, int x2, int y2)
{
    int f = abs(x2 - x1);
    int b = abs(y2 - y1);
 
    return (f == 2 && b == 1) || (f == 1 && b == 2);
}
 
int Judge(char s1[3], char s2[3])
{
    int x = s2[0] - 'A';
    int y = s2[1] - '1';
 
    if (board[x][y] != 0)
        return 1;
    board[x][y] = 1;
 
    return !CanMove(s1[0] - 'A', s1[1] - '1',x,y);
}
 
 
 
void CopyValue(char to[3], char from[3])
{
    for (int i = 0; i < 3; i++)
        to[i] = from[i];
}
 
int main()
{
    char str1[3];
    char str2[3];
 
    scanf("%s", str1);
 
    int x = str1[0] - 'A';
    int y = str1[1] - '1';
    board[x][y] = 1;
 
    for (int i = 1; i < 36; i++)
    {
        scanf("%s", str2);
 
        if (Judge(str1, str2))
        {
            printf("Invalid");
            return 0;
        }
 
        CopyValue(str1, str2);
    }
/*
    for (int i = 0; i < 6; i++) {
        for (int j = 0; j < 6; j++) {
            if (!board[i][j])
            {
                printf("Invalid");
                return 0;
            }
        }
    }
*/
    if (!CanMove(x, y, str2[0] - 'A', str2[1] - '1'))
    {
        printf("Invalid");
        return 0;
    }
 
    printf("Valid");
    return 0;
}