#include <algorithm> #include <array> #include <bitset> #include <iostream> #include <set> #include <string> #include <vector> using namespace std; const int max_grid_size = 8; int grid_size; array<char, max_grid_size * max_grid_size> grid; bitset<max_grid_size * max_grid_size> visited; struct GridPos { int row, col; GridPos(int row, int col) : row{row}, col{col} { } operator int() const { return row * max_grid_size + col; } vector<GridPos> unvisited_neighbors() const { int nrow_min = max(row - 1, 0), nrow_max = min(row + 2, grid_size), ncol_min = max(col - 1, 0), ncol_max = min(col + 2, grid_size); vector<GridPos> result; result.reserve(9); for (int nrow = nrow_min; nrow < nrow_max; nrow++) { for (int ncol = ncol_min; ncol < ncol_max; ncol++) { GridPos pos{nrow, ncol}; if (!visited.test(pos)) { result.push_back(pos); } } } return result; } }; bool visit(GridPos pos, const string& word, size_t depth=0) { if (grid[pos] != word[depth]) return false; if (depth == word.size() - 1) return true; bool found = false; visited.set(pos); for (auto& neighbor : pos.unvisited_neighbors()) { if (visit(neighbor, word, depth + 1)) { found = true; break; } } visited.reset(pos); return found; } bool word_in_grid(const string& word) { string search_word; char prev = '\0'; for (char c : word) { if (prev != 'q') { search_word.push_back(c); } else if (c != 'u') { return false; } prev = c; } if (prev == 'q') return false; for (int row = 0; row < grid_size; row++) { for (int col = 0; col < grid_size; col++) { if (visit(GridPos{row, col}, search_word)) { return true; } } } return false; } int main() { int num_words; string line; cin >> num_words; getline(cin, line); set<string> words; for (int i = 0; i < num_words; i++) { getline(cin, line); words.insert(line); } while (cin >> grid_size && grid_size) { getline(cin, line); for (int row = 0; row < grid_size; row++) { getline(cin, line); for (int col = 0; col < grid_size; col++) { grid[GridPos{row, col}] = line[col]; } } for (const string& word : words) { if (word_in_grid(word)) { cout << word << '\n'; } } cout << "-\n"; } }