QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#573466 | #3939. Hidden Words | LaVuna47# | AC ✓ | 29ms | 7720kb | C++17 | 3.0kb | 2024-09-18 18:54:12 | 2024-09-18 18:54:17 |
Judging History
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'