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

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

 

입력받은대로 나이트가 움직일 수 있고 마지막 칸에서 처음 칸으로 올 수 있다면 Valid, 아니면 Invalid를 출력하도록 했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int dAlp[8] = { -2,-1, 1, 2, 2, 1,-1,-2 };
int dNum[8] = {  1, 2, 2, 1,-1,-2,-2,-1 };

set<string> st;

bool CanGo(string target, string curr) {
	for (int i = 0; i < 8; i++) {
		string next = "";
		next += curr[0] + dAlp[i];
		next += curr[1] + dNum[i];
		if (next[0] < 'A' || next[0]>'F') continue;
		if (next[1] < '1' || next[1]>'6') continue;
		if (next != target) continue;
		if (st.find(next) != st.end()) continue;
		st.insert(target);
		return true;
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	
	vector<string> v(35);
	string curr, start;
	cin >> start;
	curr = start;
	st.insert(curr);
	bool isValid = true;
	for (int i = 0; i < 35; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < 35; i++) {
		string target = v[i];
		if (CanGo(v[i], curr)) {
			curr = target;
		}
		else {
			isValid = false;
			break;
		}
	}
	st.erase(start);
	if (isValid) {
		if (!CanGo(start, v[v.size() - 1])) {
			isValid = false;
		}
	}

	if (isValid) cout << "Valid";
	else cout << "Invalid";
};