[C++] 백준 1331번 나이트 투어

나이트가 모든 경로를 한번씩 거쳐서 처음 위치로 올 수 있는지 찾는 문제입니다.

이동을 할 때 다음의 규칙으로 이동이 가능합니다.
1. 이전 x좌표와 2차이, y좌표와 1차이
2. 이전 x좌표와 1차이, y좌표와 2차이
그리고 이미 이동한 곳은 체크를 해두어서 이동하지 못하도록 합니다.
과정을 반복해서 마지막 입력까지 확인을 한 뒤
마지막 위치에서 처음 위치를 다시 갈 수 있는지 체크해주면 됩니다.

 

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int main(int argc, char *argv[]) 
{
	bool flag = false;
	bool map[6][6];
	int start[2];
	int prev[2];
	string s;

	cin >> s;

	prev[0] = s[0] - 'A';
	prev[1] = s[1] - '1';
	start[0] = prev[0];
	start[1] = prev[1];

	memset(map, false, sizeof(map));

	for (int i = 1; i < 37; ++i) {
		int now[2];

		if (i == 36) {
			now[0] = start[0];
			now[1] = start[1];
		}
		else {
			cin >> s;

			now[0] = s[0] - 'A';
			now[1] = s[1] - '1';
		}		

		if (!map[now[0]][now[1]] 
            && ((abs(now[0] - prev[0]) == 1 && abs(now[1] - prev[1]) == 2) 
            || (abs(now[0] - prev[0]) == 2 && abs(now[1] - prev[1]) == 1))) {
			map[now[0]][now[1]] = true;
			prev[0] = now[0];
			prev[1] = now[1];
		}
		else {
			flag = true;
			break;
		}
	}

	if (flag) {
		cout << "Invalid" << endl;
	}
	else {
		cout << "Valid" << endl;
	}

	return 0;
}