QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#848480 | #5730. Maze Connect | LaVuna47 | AC ✓ | 44ms | 102680kb | C++20 | 3.2kb | 2025-01-08 20:45:54 | 2025-01-08 20:46:10 |
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, st_, n) for(int i = st_; i < n; ++i)
#define RFOR(i, n, end_) for(int i = (n)-1; i >= end_; --i)
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
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
/*
8 20
/\/\/\/\/\/\/\/\/\/\
\../\.\/..\.\/\/\/\/
/./\../././\.\/\/\/\
\/\/\.\/\\./\/..\../
/\/./\/\/.\..\/\/\.\
\.\.././\.\/\/./\.\/
/.../\../..\/./.../\
\/\/\/\/\/\/\/\/\/\/
14 16
......./\.......
....../..\......
...../....\.....
..../...../.....
....\..../......
.....\/\.\......
......./..\.....
....../.../.....
....\.\../......
..../..\/.......
....\/\/........
................
................
................
*/
int n,m;
vector<string> a;
vector<vector<bool>> vis;
vector<vector<int>> M;
bool is_tiny_room(int x, int y)
{
return x<n-1 && y<m-1 && a[x][y]=='/' && a[x][y+1]=='\\' && a[x+1][y]== '\\' && a[x+1][y+1]=='/';
}
bool dfs(int x, int y, int marker)
{
vis[x][y]=true;
M[x][y]=marker;
bool res=true;
if(x==0 || y==0 || x==n-1 || y==m-1)
res=false;
FOR(dx,-1,2)
{
FOR(dy,-1,2)
{
if(x+dx >=0 && x+dx<n && y+dy>=0 && y+dy<m && !vis[x+dx][y+dy] && a[x+dx][y+dy]=='.')
{
if(abs(dx)+abs(dy)==2)
{
if(abs(dx+dy)==2)
{
if(!(a[x+dx][y]=='/' && a[x][y+dy]=='/'))
res = dfs(x+dx,y+dy,marker) && res;
}
else
{
if(!(a[x+dx][y]=='\\' && a[x][y+dy]=='\\'))
res = dfs(x+dx,y+dy,marker) && res;
}
}
else
res = dfs(x+dx,y+dy,marker) && res;
}
}
}
return res;
}
int solve()
{
if(!(cin>>n>>m))return 1;
a=vector<string>(n);
vis=vector<vector<bool>>(n, vector<bool>(m,false));
M=vector<vector<int>>(n, vector<int>(m,0));
FOR(i,0,n)
cin>>a[i];
int ctr=0;
int marker=0;
FOR(i,0,n)
{
FOR(j,0,m)
{
if(is_tiny_room(i,j))
++ctr;
if(a[i][j]=='.')
{
if(!vis[i][j])
{
ctr += dfs(i,j, ++marker);
}
}
}
}
//FOR(i,0,n)
//{
//FOR(j,0,m)
//{
//cout<<M[i][j]<<' ';
//}
//cout<<'\n';
//}
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
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
input:
2 2 /\ \/
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3688kb
input:
4 4 /\.. \.\. .\/\ ..\/
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
2 2 \/ /\
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
8 20 /\/\/\/\/\/\/\/\/\/\ \../\.\/./././\/\/\/ /./\.././\/\.\/\/\/\ \/\/\.\/\/./\/..\../ /\/./\/\/./..\/\/..\ \.\.././\.\/\/./\.\/ /.../\../..\/./.../\ \/\/\/\/\/\/\/\/\/\/
output:
26
result:
ok single line: '26'
Test #5:
score: 0
Accepted
time: 5ms
memory: 8972kb
input:
1000 1000 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
499001
result:
ok single line: '499001'
Test #6:
score: 0
Accepted
time: 2ms
memory: 8728kb
input:
1000 1000 \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...
output:
499000
result:
ok single line: '499000'
Test #7:
score: 0
Accepted
time: 25ms
memory: 8680kb
input:
1000 1000 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
122943
result:
ok single line: '122943'
Test #8:
score: 0
Accepted
time: 1ms
memory: 4104kb
input:
100 100 ................................................./\................................................. ................................................/..\................................................ .............................................../....\........................................
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3756kb
input:
100 100 ................................................./\................................................. ................................................/..\................................................ ..............................................././\.\........................................
output:
25
result:
ok single line: '25'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
40 40 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\...
output:
760
result:
ok single line: '760'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
40 40 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\...
output:
760
result:
ok single line: '760'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
21 21 /\/\/\/\/\/\/\/\/\/\. \...\...\...\...\...\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\....
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 16ms
memory: 54940kb
input:
997 997 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
10 10 ..../\.... .../..\... .././\.\.. ././..\.\. /././\.\.\ \.\.\/././ .\.\.././. ..\.\/./.. ...\../... ....\/....
output:
3
result:
ok single line: '3'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
10 11 ...../\.... ..../..\... ..././\.\.. .././..\.\. ./././\.\.\ .\.\.\/././ ..\.\.././. ...\.\/./.. ....\../... .....\/....
output:
3
result:
ok single line: '3'
Test #16:
score: 0
Accepted
time: 37ms
memory: 102680kb
input:
1000 1000 .....................................................................................................................................................................................................................................................................................................
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
100 100 ././././././././././././././././././././././././././././././././././././././././././././././././././ /./././././././././././././././././././././././././././././././././././././././././././././././././. ./././././././././././././././././././././././././././././././././././././././././././././...
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
100 100 .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\ \.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\. .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\...
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3948kb
input:
100 100 .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\ ././././././././././././././././././././././././././././././././././././././././././././././././././ .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\...
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
4 4 /\/\ \/\/ /\/\ \/\/
output:
5
result:
ok single line: '5'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
3 3 /\. \/\ .\/
output:
2
result:
ok single line: '2'
Test #22:
score: 0
Accepted
time: 44ms
memory: 52564kb
input:
1000 1000 \/..\../..\/\/./......./..././..\../.../....\.\/././......./././.../..........\...\/.../..\.\../......\.....\.\/..\.././..\...\/...../.../\/./..\.......\../..\/\/..\/...../..././\/./..././................\....../..\....../././.../....\...\/....\.\/......\.......\../.../....\.\/..\....../.....
output:
86
result:
ok single line: '86'
Test #23:
score: 0
Accepted
time: 29ms
memory: 28012kb
input:
1000 500 /\.\...\/\...././....././\.\.....\.\/././\../......\...\.\.......\/././....\.././......./.../.../\.........\/....\../..\.....\........../\/\.....\/......./..\/......./........\.....\...\...\/./...../..\/......\..../.........../..\.\...././..........\/././\......../\/........\....../\...\../...
output:
722
result:
ok single line: '722'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3784kb
input:
100 100 \/\/\/\/\/.../.../\/\.\/\.\/\/.../././\.\../././\........../..\/..././.../..\.\.......\/\..../\..../ /./\/\.\/...../.../\..../\../..\/.../..././.../..\...\../\/\.\../\/././..\/...../....././....\/././\ \/\.\...\/....\/.../......\/\.\.\...\/..\.\/\/..\../..\...\/\/\/./\../....\/\/./.../\/\../...
output:
184
result:
ok single line: '184'
Test #25:
score: 0
Accepted
time: 5ms
memory: 7320kb
input:
250 250 /\............/..\........../.../....././\....../....\.....\............................../.../.../..........\...\....../....\...\/........\.\/./...../..........\..../............\..../....\...\.......././....\.\................../...../..\.\/..\.\/\ ..\...\/...../\...\.......\.\.\/./\.\/......
output:
6
result:
ok single line: '6'
Test #26:
score: 0
Accepted
time: 20ms
memory: 20076kb
input:
500 1000 /\.\/\../....\/\.\/..././.../\/....\.././\/..\.\/..\/..\...\...\/....././....\.\.\.\.\.././\/./..\/.../..\/..\.\/./....\/./..\...\/..\/.../\..../..\/..\.\.\.....\/.../..\.\...\.\/........\/./..\...\/./...../\.\/././....\/..\/./\.\.\/././\/..\/./.../\...././..\/././...../\/\../..\/./\../.......
output:
2762
result:
ok single line: '2762'
Test #27:
score: 0
Accepted
time: 12ms
memory: 15448kb
input:
500 500 \...\../..\...\/...../\....../..\.....././....\/.../........\...\...\/./.../..././.../......\../\/....\...\../..\...\/..........\.././...../...../..\...\...\..../..\.\.....\/............\...\/\/..\.............\....../\/.../././\.....././.../............\..../\/./..\.\......../..\.....\../.....
output:
663
result:
ok single line: '663'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3952kb
input:
50 50 /\.\.\.\.././.../..././.../\.....\/..\/\.\...\.... ...../\.....\.\/./\/......./\..../..\/..\.\/./\../ ..../\.\/\..../..\.\../........\/....\.././\...\/\ \/\/././\...\/./\/........\.....\/\/./..\...\/\... ...\/...../\.........\/..\.\...\/.../.../\../..\.. \../....\../..\.././././\.\../...../......
output:
21
result:
ok single line: '21'