開啟章節選單

10010 Where's Waldorf?

題目翻譯

給你一個字母矩陣，接著給多個查詢單字。
對每個單字，請在矩陣中找出它第一次出現的位置（以列優先、行優先掃描），比對時不分大小寫，方向可以是 8 個方向（上下左右與 4 個對角）。

輸出該單字起點的座標（1-based）。

輸入

第一行是一個整數，代表測試案例的數量，隨後有一個空行。
每個案例第一行是兩個整數 m 與 n (1≤m,n≤50)(1 \le m, n \le 50)，代表網格的列數與欄數。
接下來 m 行每行有 n 個字母。
隨後是一個整數 k (1≤k≤20)(1 \le k \le 20)，代表要搜尋的單字數量。
接下來 k 行每行包含一個單字。
每筆測資之間會有一個空行。

輸出

對於每個要搜尋的單字，輸出其在網格中「第一個字母」的座標（列與行，從 1 開始）。
若單字多次出現，輸出座標值最小的那一個（先比列，再比行）。
每個案例的輸出之間請留一個空行。

解題思路

這份程式是標準的暴力搜尋：

  1. 先把整張表與每個查詢字串都轉成小寫，避免大小寫判斷。
  2. 對每個查詢字串，從左上到右下掃每個格子，只有當起始字元相同才繼續。
  3. 從該格往 8 個方向逐字檢查；只要有一個方向完整匹配，就輸出座標並停止該查詢。

由於題目資料量不大，這樣的暴力法足夠通過，實作也直觀。

程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define idonthavegirlfriend ios::sync_with_stdio(0), cin.tie(0);
#define pb push_back
#define yn(a) (a ? "Yes\n" : "No\n")
// #include <atcoder/fenwicktree>
// #include <atcoder/dsu>
// using namespace atcoder
// Jackis666

signed main() {
    idonthavegirlfriend
    int t;
    cin >> t;
    while (t--) {
        int n, m, q;
        cin >> n >> m;
        vector<string> a(n);
        for (auto& c : a) cin >> c;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                a[i][j] = tolower(a[i][j]);
            }
        }
        cin >> q;
        int dx[8] = {1, 1, 1, -1, -1, -1, 0, 0};
        int dy[8] = {1, 0, -1, 1, 0, -1, 1, -1};
        while (q--) {
            string s;
            cin >> s;
            for (int i = 0; i < s.size(); i++) s[i] = tolower(s[i]);
            bool okk = true;
            for (int i = 0; i < n and okk; i++) {
                for (int j = 0; j < m and okk; j++) {
                    if (a[i][j] != s[0]) continue;
                    for (int k = 0; k < 8 and okk; k++) {
                        bool ok = true;
                        int nowx = i;
                        int nowy = j;
                        for (int ss = 1; ss < s.size(); ss++) {
                            nowx += dx[k];
                            nowy += dy[k];
                            if (nowx < 0 or nowx >= n or nowy < 0 or
                                nowy >= m) {
                                ok = false;
                                break;
                            }
                            if (a[nowx][nowy] != s[ss]) {
                                ok = false;
                                break;
                            }
                        }
                        if (ok) {
                            cout << i + 1 << " " << j + 1 << "\n";
                            okk = false;
                            break;
                        }
                    }
                }
            }
        }
        if (t) cout << "\n";
    }
}

在遇到巢狀迴圈要中途跳離時
如果覺得需要多維護一個狀態不太好寫
可以嘗試把它包成一個 solve()，這樣就可以直接 return 並且維持執行多筆測資了

//author: Piau
#include <bits/stdc++.h>
using namespace std;

#define WA() cin.tie(0)->sync_with_stdio(0)
#define int long long

void solve(int n, int m, vector<string> &v) {
    string s; cin >> s;
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++)
    for (int mx = -1; mx <= 1; mx++) for (int my = -1; my <= 1; my++) if (mx || my) {
        int x = i, y = j, k = 0;
        for (; k < s.size() && x >= 0 && x < n && y >= 0 && y < m; k++, x += mx, y += my) if (tolower(v[x][y]) != tolower(s[k])) break;
        if (k == s.size()) return cout << i+1 << ' ' << j+1 << '\n', void();
    }
}

signed main() { WA();
    int t; for (cin >> t; t--;) {
        int n, m; cin >> n >> m;
        vector<string> v(n);
        for (auto &i : v) cin >> i;
        int q; for (cin >> q; q--;) solve(n, m, v);
        if (t) cout << '\n';
    }
}