QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#573466#3939. Hidden WordsLaVuna47#AC ✓29ms7720kbC++173.0kb2024-09-18 18:54:122024-09-18 18:54:17

Judging History

This is the latest submission verdict.

  • [2024-09-18 18:54:17]
  • Judged
  • Verdict: AC
  • Time: 29ms
  • Memory: 7720kb
  • [2024-09-18 18:54:12]
  • Submitted

answer

/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define RFOR(i, n) for(int i = n-1; i >= 0; --i)
#define output_vec(vec) { FOR(i_, sz(vec)) cout << vec[i_] << ' '; cout << '\n'; }
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<bool> vb;
typedef short si;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

int n, m;
vector<string> a;
bool vis[11][11];
unordered_map<string, bool> dp;

bool f(int x, int y, int p, const string& s)
{
    if(p == sz(s)-1)
        return true;
    vis[x][y] = true;
    bool res = false;
    if(x-1 >= 0 && !vis[x-1][y] && a[x-1][y] == s[p+1])
    {
        res = f(x-1, y, p+1, s);
        if(res) return res;
    }
    if(x+1 < n && !vis[x+1][y] && a[x+1][y] == s[p+1])
    {
        res = f(x+1, y, p+1, s);
        if(res) return res;
    }
    if(y-1 >= 0 && !vis[x][y-1] && a[x][y-1] == s[p+1])
    {
        res = f(x, y-1, p+1, s);
        if(res) return res;
    }
    if(y+1 < m && !vis[x][y+1] && a[x][y+1] == s[p+1])
    {
        res = f(x, y+1, p+1, s);
        if(res) return res;
    }
    vis[x][y] = false;
    return false;
}

bool contains(const string& s)
{
    auto it = dp.find(s);
    if(it != dp.end())
        return it->second;
    for(auto& item: vis)
        for(auto& i: item) i = false;
    
    FOR(i, n)
    {
        FOR(j, m)
        {
            if(s[0] == a[i][j] && f(i, j, 0, s))
                return true;
        }
    }
    return dp[s] = false;
}

int solve()
{
    if(!(cin >> n >> m))
        return 1;
    a = vector<string>(n);
    FOR(i, n)
        cin >> a[i];
    int q;
    cin >> q;
    int ctr = 0;
    FOR(_, q)
    {
        string s;
        cin >> s;
        if(contains(s))
            ++ctr;
    }
    cout << ctr << '\n';
    return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1e9;
    //cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        if (solve())
        {
            break;
        }
#ifdef ONPC
        cout << "__________________________" << endl;
#endif
    }
#ifdef ONPC
    cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3756kb

input:

4 4
SNKO
VRER
IDIN
NEGU
3
KORN
NEDI
DER

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 2ms
memory: 4572kb

input:

9 6
ILACFP
TBKRMV
GILOYK
VBOKQM
QGBDNG
GPDEFB
JVMDDU
TRQKEX
IBSQEX
20802
YSTKCIV
TSZD
NHKHWDY
LITGVQG
ALITGV
YVCSN
DKAFYHPDG
FECAH
JKAKGT
WQKMSS
TJVRB
YQI
JKSVTSO
MCJL
UQCVQM
XPWCMBXZH
WW
FSW
TRBSQMD
IXMCG
PEDIJSL
REWBUXZ
DLIZQHV
NKH
HDZHY
LMGK
FUK
YMRKL
TIPCAJ
TXQHP
BLACR
HYPIBER
OS
SIQAXTZ
AVNKNYU...

output:

6129

result:

ok single line: '6129'

Test #3:

score: 0
Accepted
time: 2ms
memory: 4032kb

input:

6 7
EIJURVC
ZAQBCFH
JKJDSLY
BPXYYSL
IZCBBNM
BTPOGZM
7804
CHYL
LSLY
OGBYS
FLWLAMP
WBMCVY
Y
UXDK
TTXKFK
ZCEY
KPXJDS
MVAMIQZ
EKSR
QBCRV
WWVBZOM
XJKJ
TAZFBEU
UCCN
BTP
GZNSLF
VERMZV
PTZIBJ
MIEG
GDAWBA
XVKUUL
WOSRJ
ZJUYG
RSULLB
VVLAI
MMNZ
KWJ
YRJ
HA
UVENBN
KROZHM
GSYSK
ESMW
VFCB
KGHIM
PBU
XJDBQ
TWNHQSE
ID...

output:

2516

result:

ok single line: '2516'

Test #4:

score: 0
Accepted
time: 27ms
memory: 6924kb

input:

10 10
NHYEUHCRKW
CMMQNZIBJI
WQDIUAPJUM
UUBGCQUBOY
XJVYZTJZCK
EPJIRVVBNW
VSFTURCVXD
UYSIRRIBHN
RXPLGMQEMX
THDZEEIJGL
87402
QSCEZ
JIRUMDSZLB
CRBJBO
SSKUG
NBZCKWDXH
KWOGMJKJCI
PDZLGE
PEPVOZWZNL
WFBGCT
OLFDTSKGF
QZBNBJYFJ
IKRUW
ZNUCGYVJI
MMQEY
OQSJZGSX
SBMP
RVFE
CDMN
DNBMY
EYHMCWQU
BDMY
VRZYVBU
TJVVRITF...

output:

39112

result:

ok single line: '39112'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3968kb

input:

6 5
KJOEQ
VBJFM
BRYLL
FSRVY
ULSID
AXTSN
2345
NSIS
SFULX
MCPXY
EIG
YVL
JOEQ
BRJ
XZRXT
OAINN
QATVZ
MWQ
CJ
ZCP
TW
ISLXA
DVYMQ
NFR
YYYS
RZSZO
KJKJ
ATRJ
SXW
CP
IRUR
XMP
JOJF
SIDN
GIT
FBRB
FEG
JZZTF
BET
HK
IIAL
KJOEQ
ZIQYA
LMQE
SFBV
JFLL
RFQEG
GFJXL
NNMQ
FULS
YYEXY
ZTW
VBK
MFEQ
BRSR
BVKJ
EBXSK
EJR
IMBGS
T...

output:

799

result:

ok single line: '799'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3800kb

input:

5 9
KOZNXMOES
OFTEVRNUC
XHKZBWMNQ
YADDMCKJV
EOTOUUUEG
4573
QGRJ
WRUFW
UNRWMKJ
TDWYNQEFX
SCQVJ
DZEVB
YPV
CD
MIYC
OEUNRV
VCEGGUTMS
CSEON
EBLSCHEZ
ALJWKS
NQCUN
CKMNO
NXVBZD
GIAERDN
LLQSFCS
QK
MLEB
NUCQVGEJ
KOFHXYEO
XOKOZTF
NDJHHLGB
QCVPG
SEUCQ
XMBELU
MCYR
FTZNXMRW
VENX
MZEO
BGOHA
NQZQGT
OQMWLU
DKTEZ
AD...

output:

2014

result:

ok single line: '2014'

Test #7:

score: 0
Accepted
time: 29ms
memory: 7552kb

input:

10 10
HLWXUALSMP
VFRLCQJPQY
PWSFFRNBFC
RHVRLATTIJ
IUMWUUKSKZ
OUINIYVKMD
AGEIIDDECF
BYWSSUSITN
WFYQYHEAGT
OKDLEWQXMU
100000
FWKJCCWV
HFT
EXHIN
UQOLJKK
JSUZKVUAR
TKSTBPQYP
AXMUTGTIE
KHRZZIVS
HFRQOVSHS
DKRRVOMK
MDFCTIAXQ
VDBOT
DFSAFCTOE
TIKMD
PYCFBPQM
LRS
EYSUSIE
QFULRRT
EHYSIDDVK
ITBNTKSKZ
GDQPIJFFS
E...

output:

42023

result:

ok single line: '42023'

Test #8:

score: 0
Accepted
time: 27ms
memory: 7720kb

input:

10 10
WSLBOKGWMW
KYIICHMEOI
ZJCVMYJUSH
YPTOCIVBVX
UUIMJWDAHZ
GFWBWCUJMN
ZNZHGBTBDT
EUXJWIJNDX
YVZOTENPPM
BJARBSIZIA
100000
IVBADWCUJM
GHBMOCIYJV
DDFYXWTTK
AEFTKW
XMAIZPNIS
BVBJ
EYXGPARQL
TMI
ZYPUFNZEY
XMM
FKE
YNENOOFPZ
ABUJVD
ISEIBC
KWFPPT
PXGJHP
QVHWJHKU
LBIICJPYUG
TMNYLPGBE
WBWGWJ
TIXQMST
OQUQ
DUZ...

output:

40885

result:

ok single line: '40885'

Test #9:

score: 0
Accepted
time: 7ms
memory: 3644kb

input:

10 10
ABABABABAB
BABABABABA
ABABABABAB
BABABABABA
ABABABABAB
BABABABABA
ABABABABAB
BABABABABA
ABABABABAB
BABABABABA
100000
ABABABABAA
BABABABABB
ABABABABAA
BABABABABB
ABABABABAA
BABABABABB
ABABABABAA
BABABABABB
ABABABABAA
BABABABABB
ABABABABAA
BABABABABB
ABABABABAA
BABABABABB
ABABABABAA
BABABABABB
A...

output:

0

result:

ok single line: '0'