#include #include using namespace std; struct Card { Card(): visited(false) {}; list connect; bool visited; }; struct CardItem { CardItem(): depth(0), prev(nullptr) {}; Card* card; int depth; CardItem* prev; }; int numberToIndex(char n) { if (n >= '2' && n <= '9') { return n - '2'; } switch(n) { case 'X': return 8; case 'J': return 9; case 'Q': return 10; case 'K': return 11; case 'A': return 12; } cout << "error!" << (int)n << endl; } int colorToIndex(char n) { switch (n) { case 'C': return 0; case 'D': return 1; case 'H': return 2; case 'S': return 3; } cout << "error2!" << n << endl; } int main() { Card start; while (true) { string line; list numbersList[13]; list colorsList[4]; list toBeDeletedCards; list cardsToTry; int cards; if (!(cin >> cards)) break; int expectedDepth = -1; for (int i = 0; i < cards; ++ i) { char number, color; string nc; cin >> nc; number = nc[0]; color = nc[1]; //cout << (char)number << ", " << color << endl; Card* newCard = new Card(); toBeDeletedCards.push_back(newCard); // connect all relevant for (auto j = numbersList[numberToIndex(number)].begin(); j != numbersList[numberToIndex(number)].end(); ++ j) { newCard->connect.push_back(*j); (*j)->connect.push_back(newCard); } for (auto j = colorsList[colorToIndex(color)].begin(); j != colorsList[colorToIndex(color)].end(); ++ j) { newCard->connect.push_back(*j); (*j)->connect.push_back(newCard); } expectedDepth ++; // insert the card numbersList[numberToIndex(number)].push_back(newCard); colorsList[colorToIndex(color)].push_back(newCard); cardsToTry.push_back(newCard); } if (expectedDepth == 0) { cout << "YES" << endl; continue; } bool found = false; for (auto startCard = cardsToTry.begin(); startCard != cardsToTry.end(); ++ startCard) { // bfs CardItem root; root.card = (*startCard); list cardQueue; cardQueue.push_back(&root); list toBeDeleted; root.card->visited = true; for (auto x = cardsToTry.begin(); x != cardsToTry.end(); ++ x) { (*x)->visited = false; } while (!cardQueue.empty()) { CardItem* curCard = cardQueue.front(); cardQueue.pop_front(); //cout << curCard->depth << endl; for (auto i = curCard->card->connect.begin(); i != curCard->card->connect.end(); ++ i) { bool isVisited = false; CardItem* curCardItem = curCard; while (curCardItem != nullptr) { if (curCardItem->card == (*i)) { isVisited = true; break; } curCardItem = curCardItem->prev; } if (!isVisited) { (*i)->visited = true; CardItem* newItem = new CardItem(); newItem->prev = curCard; newItem->depth = curCard->depth + 1; newItem->card = (*i); if (newItem->depth == expectedDepth) { cout << "YES" << endl; found = true; break; } cardQueue.push_back(newItem); toBeDeleted.push_back(newItem); } } if (found) break; } for (auto j = toBeDeleted.begin(); j != toBeDeleted.end(); ++ j) { delete (*j); } if (found) break; } if (!found) { cout << "NO" << endl; } for (auto j = toBeDeletedCards.begin(); j != toBeDeletedCards.end(); ++ j) { delete (*j); } } return 0; }