Hướng dẫn giải của Bedao Mini Contest 08 - WORDSEARCH


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: bedao

Với mỗi truy vấn, ta chỉ cần thử mọi vị trí có thể của xâu ~S~ rồi kiểm tra. Cần code cẩn thận để tránh truy cập tràn mảng.

Độ phức tạp: ~\mathcal{O}(n \times m \times q \times max(n, m))~.

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

int n, m, q;
char a[105][105];

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("sol.inp", "r", stdin);
    // freopen("sol.out", "w", stdout);

    cin >> n >> m >> q;
    for1(i,1,n) {
        for1(j,1,m) cin >> a[i][j];
    }

    while (q--) {
        string s;
        cin >> s;

        for1(i,1,n) {
            for1(j,1,m) {
                bool flag = 1;
                for1(k,0,sz(s) - 1) {
                    if (j + k > m || a[i][j + k] != s[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cout << "YES\n";
                    goto nxt;
                }

                flag = 1;
                for1(k,0,sz(s) - 1) {
                    if (j - k < 1 || a[i][j - k] != s[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cout << "YES\n";
                    goto nxt;
                }

                flag = 1;
                for1(k,0,sz(s) - 1) {
                    if (i + k > n || a[i + k][j] != s[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cout << "YES\n";
                    goto nxt;
                }

                flag = 1;
                for1(k,0,sz(s) - 1) {
                    if (i - k < 1 || a[i - k][j] != s[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cout << "YES\n";
                    goto nxt;
                }

                flag = 1;
                for1(k,0,sz(s) - 1) {
                    if (i + k > n || j + k > m || a[i + k][j + k] != s[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cout << "YES\n";
                    goto nxt;
                }

                flag = 1;
                for1(k,0,sz(s) - 1) {
                    if (i - k < 1 || j - k < 1 || a[i - k][j - k] != s[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cout << "YES\n";
                    goto nxt;
                }

                flag = 1;
                for1(k,0,sz(s) - 1) {
                    if (i + k > n || j - k < 1 || a[i + k][j - k] != s[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cout << "YES\n";
                    goto nxt;
                }

                flag = 1;
                for1(k,0,sz(s) - 1) {
                    if (i - k > n || j + k < 1 || a[i - k][j + k] != s[k]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    cout << "YES\n";
                    goto nxt;
                }

            }
        }

        cout << "NO\n";
        nxt:;
    }

}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.