Bad News

    1#include <bits/stdc++.h>
    2 
    3using namespace std;
    4 
    5int n, q;
    6vector<vector<char>> grid;
    7vector<vector<bool>> visited; 
    8const vector<pair<int,int>> dirs = {{-1, -1}, {-1, 0}, {-1, 1},{0, -1},{0, 1},{1, -1}, {1, 0}, {1, 1}};
    9 
    10bool dfs(int x, int y, const string &w, int idx) {
    11    visited[x][y] = true;
    12    if (idx == (int) w.size() - 1) {
    13        visited[x][y] = false;
    14        return true;
    15    }
    16    for (auto [dx, dy] : dirs) {
    17        int nx = x + dx;
    18        int ny = y + dy;
    19        if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny] || grid[nx][ny] != w[idx + 1]) 
    20            continue;
    21        if (dfs(nx, ny, w, idx + 1)) {
    22            visited[x][y] = false;
    23            return true;
    24        }
    25    }
    26    // does not exist
    27    visited[x][y] = false;
    28    return false;
    29}
    30int main(){
    31    ios::sync_with_stdio(0);
    32    cin.tie(0);
    33    cin >> n >> q;
    34    grid.resize(n);
    35    for(int i = 0; i < n; i++)grid[i].resize(n);
    36    visited.assign(n, vector<bool>(n, false));
    37    for(int i = 0; i < n; i++){
    38        for(int j = 0; j < n; j++){
    39            cin >> grid[i][j];
    40        }
    41    }
    42    string _;
    43    getline(cin, _);
    44    while(q--> 0){
    45        string word;
    46        getline(cin, word);
    47        for (char &c : word) c = tolower(c);
    48        bool found = false;
    49        for (int i = 0; i < n && !found; i++) {
    50            for (int j = 0; j < n && !found; j++) {
    51                if (grid[i][j] == word[0]) {
    52                    // reset visited
    53                    for (auto &k : visited) 
    54                        fill(k.begin(), k.end(), false);
    55                    if (dfs(i, j, word, 0)) {
    56                        found = true;
    57                    }
    58                }
    59            }
    60        }
    61        cout << (found ? "good puzzle!\n" : "bad puzzle!") << '\n';
    62    }
    63    return 0;
    64}