#hash_set

// Game of Boggle #include <string> #include <iostream> #include <vector> #include <hash_set> using namespace std; typedef unsigned long ULONG; typedef long LONG; typedef bool BOOLEAN; typedef struct _BOGGLE_WORD { ULONG Begin[2]; ULONG End[2]; wstring strWord; }BOGGLE_WORD; typedef vector<BOGGLE_WORD> BOGGLE_WORD_LIST; typedef hash_set<wstring> DICTIONARY; typedef vector<vector<wchar_t>> BOGGLE_GRID; class CBoggle { private: BOGGLE_WORD_LIST CheckRow( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Row ); BOGGLE_WORD_LIST CheckColumn( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Column ); BOGGLE_WORD_LIST CheckForwardDiag( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Dist ); BOGGLE_WORD_LIST CheckBackwardDiag( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Dist ); public: BOGGLE_WORD_LIST FindWordsinBoggle( __in DICTIONARY Dictionary, __in BOGGLE_GRID BoggleGrid ); void PrintBoggleWords( __in BOGGLE_WORD_LIST BoggleWordList ); }; void CBoggle::PrintBoggleWords( __in BOGGLE_WORD_LIST BoggleWordList ) { for (ULONG WordIter = 0; WordIter < BoggleWordList.size(); WordIter++) { wcout<<"("<<BoggleWordList[WordIter].Begin[0]<<","<<BoggleWordList[WordIter].Begin[1]<<") to "; wcout<<"("<<BoggleWordList[WordIter].End[0]<<","<<BoggleWordList[WordIter].End[1]<<") "; wcout<<BoggleWordList[WordIter].strWord.data()<<endl; } } BOGGLE_WORD_LIST CBoggle::CheckRow( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Row ) { BOGGLE_WORD_LIST BoggleWordList; wstring strRow = L""; for (ULONG Column = 0; Column < BoggleGrid[Row].size(); Column++) { strRow += BoggleGrid[Row][Column]; } for (ULONG Begin = 0; Begin < strRow.size(); Begin++) { for (ULONG End = Begin; End < strRow.size(); End++) { wstring strSub = strRow.substr(Begin, End-Begin+1); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row; BoggleWord.Begin[1] = Begin; BoggleWord.End[0] = Row; BoggleWord.End[1] = End; BoggleWord.strWord = strSub; // wcout<<"Row: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } reverse(strSub.begin(), strSub.end()); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row; BoggleWord.Begin[1] = End; BoggleWord.End[0] = Row; BoggleWord.End[1] = Begin; BoggleWord.strWord = strSub; // wcout<<"Row Reverse: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } } } return BoggleWordList; } BOGGLE_WORD_LIST CBoggle::CheckColumn( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Column ) { BOGGLE_WORD_LIST BoggleWordList; wstring strColumn = L""; for (ULONG Row = 0; Row < BoggleGrid.size(); Row++) { strColumn += BoggleGrid[Row][Column]; } for (ULONG Begin = 0; Begin < strColumn.size(); Begin++) { for (ULONG End = Begin; End < strColumn.size(); End++) { wstring strSub = strColumn.substr(Begin, End-Begin+1); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Begin; BoggleWord.Begin[1] = Column; BoggleWord.End[0] = End; BoggleWord.End[1] = Column; BoggleWord.strWord = strSub; // wcout<<"Column: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } reverse(strSub.begin(), strSub.end()); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = End; BoggleWord.Begin[1] = Column; BoggleWord.End[0] = Begin; BoggleWord.End[1] = Column; BoggleWord.strWord = strSub; // wcout<<"Column Reverse: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } } } return BoggleWordList; } BOGGLE_WORD_LIST CBoggle::CheckForwardDiag( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Dist ) { BOGGLE_WORD_LIST BoggleWordList; ULONG Row = (ULONG)(std::max<int>(BoggleGrid.size() - 1 - Dist, 0)); ULONG Column = (ULONG)(std::max<int>(Dist - BoggleGrid.size() + 1, 0)); wstring strDiag = L""; ULONG RowIter = Row; ULONG ColIter = Column; while (true) { if (RowIter >= BoggleGrid.size() || ColIter >= BoggleGrid[Row].size()) { break; } strDiag += BoggleGrid[RowIter++][ColIter++]; } for (ULONG Begin = 0; Begin < strDiag.size(); Begin++) { for (ULONG End = Begin; End < strDiag.size(); End++) { wstring strSub = strDiag.substr(Begin, End-Begin+1); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row + Begin; BoggleWord.Begin[1] = Column + Begin; BoggleWord.End[0] = Row + End; BoggleWord.End[1] = Column + End; BoggleWord.strWord = strSub; // wcout<<"Forward diag: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } reverse(strSub.begin(), strSub.end()); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row + End; BoggleWord.Begin[1] = Column + End; BoggleWord.End[0] = Row + Begin; BoggleWord.End[1] = Column + Begin; BoggleWord.strWord = strSub; // wcout<<"Forward Diag Reverse: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } } } return BoggleWordList; } BOGGLE_WORD_LIST CBoggle::CheckBackwardDiag( __in BOGGLE_GRID BoggleGrid, __in DICTIONARY Dictionary, __in ULONG Dist ) { BOGGLE_WORD_LIST BoggleWordList; ULONG Row = std::max<LONG>(Dist - BoggleGrid[0].size() - 1, 0); LONG Column = 0; if (Dist >= BoggleGrid[0].size()) { Column = BoggleGrid[0].size()-1; } wstring strDiag = L""; ULONG RowIter = Row; LONG ColIter = Column; while (true) { if (RowIter >= BoggleGrid.size() || ColIter < 0) { break; } strDiag += BoggleGrid[RowIter++][ColIter--]; } for (ULONG Begin = 0; Begin < strDiag.size(); Begin++) { for (ULONG End = Begin; End < strDiag.size(); End++) { wstring strSub = strDiag.substr(Begin, End-Begin+1); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row + Begin; BoggleWord.Begin[1] = Column - Begin; BoggleWord.End[0] = Row + End; BoggleWord.End[1] = Column - End; BoggleWord.strWord = strSub; // wcout<<"Backward Diag: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } reverse(strSub.begin(), strSub.end()); if (Dictionary.find(strSub) != Dictionary.end()) { BOGGLE_WORD BoggleWord = {0}; BoggleWord.Begin[0] = Row + End; BoggleWord.Begin[1] = Column - End; BoggleWord.End[0] = Row + Begin; BoggleWord.End[1] = Column - Begin; BoggleWord.strWord = strSub; // wcout<<"Backward diag reverse: "<<strSub.data()<<endl; BoggleWordList.push_back(BoggleWord); } } } return BoggleWordList; } BOGGLE_WORD_LIST CBoggle::FindWordsinBoggle( __in DICTIONARY Dictionary, __in BOGGLE_GRID BoggleGrid ) { BOGGLE_WORD_LIST BoggleWordList; BOGGLE_WORD_LIST AppendWordList; for (ULONG Row = 0; Row < BoggleGrid.size(); Row++) { AppendWordList = CheckRow(BoggleGrid, Dictionary, Row); BoggleWordList.insert(BoggleWordList.end(), AppendWordList.begin(), AppendWordList.end()); } for (ULONG Column = 0; Column < BoggleGrid[0].size(); Column++) { AppendWordList = CheckColumn(BoggleGrid, Dictionary, Column); BoggleWordList.insert(BoggleWordList.end(), AppendWordList.begin(), AppendWordList.end()); } for (ULONG Dist = 0; Dist < BoggleGrid.size()+BoggleGrid[0].size()-1; Dist++) { AppendWordList = CheckForwardDiag(BoggleGrid, Dictionary, Dist); BoggleWordList.insert(BoggleWordList.end(), AppendWordList.begin(), AppendWordList.end()); } for (ULONG Dist = 0; Dist < BoggleGrid.size() + BoggleGrid[0].size()-1; Dist++) { AppendWordList = CheckBackwardDiag(BoggleGrid, Dictionary, Dist); BoggleWordList.insert(BoggleWordList.end(), AppendWordList.begin(), AppendWordList.end()); } PrintBoggleWords(BoggleWordList); return BoggleWordList; }