QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134684 | #5730. Maze Connect | Nicolas125841 | AC ✓ | 51ms | 148788kb | C++17 | 2.7kb | 2023-08-04 14:58:02 | 2023-08-04 14:58:03 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define inBounds(r, c, rcap, ccap) ((r) >= 0 && (c) >= 0 && (r) < (rcap) && (c) < (ccap))
bool flood(vector<vector<int>> &grid, vector<vector<bool>> &vis, int r, int c){
bool isIso = true;
vis[r][c] = true;
if(r > 0 && !(grid[r][c] & 4)){
if(!vis[r-1][c]){
isIso = isIso & flood(grid, vis, r-1, c);
}
}else if(!(grid[r][c] & 4)){
isIso = false;
}
if(c > 0 && !(grid[r][c] & 1)){
if(!vis[r][c-1]){
isIso = isIso & flood(grid, vis, r, c-1);
}
}else if(!(grid[r][c] & 1)){
isIso = false;
}
if(r < grid.size()-1 && !(grid[r][c] & 2)){
if(!vis[r+1][c]){
isIso = isIso & flood(grid, vis, r+1, c);
}
}else if(!(grid[r][c] & 2)){
isIso = false;
}
if(c < grid[0].size()-1 && !(grid[r][c] & 8)){
if(!vis[r][c+1]){
isIso = isIso & flood(grid, vis, r, c+1);
}
}else if(!(grid[r][c] & 8)){
isIso = false;
}
return isIso;
}
int main(){
cin.tie(NULL)->sync_with_stdio(false);
int r, c;
cin >> r >> c;
vector<vector<char>> grid(r, vector<char>(c));
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
cin >> grid[i][j];
bool isOdd = false;
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
if((i + j) % 2 && grid[i][j] == '/')
isOdd = true;
if(isOdd){
r++;
grid.insert(grid.begin(), vector<char>(c, '.'));
}
vector<vector<int>> ngrid((r + c - 1) / 2, vector<int>((r + c - 1) / 2, 0));
for(int i = 0; i < (r + c - 1) / 2; i++){
int cr = i - (c-1)/2;
int cc = (c-1)/2 - i;
for(int j = 0; j < (r + c - 1) / 2; j++){
if(inBounds(cr, cc, r, c) && grid[cr][cc] == '/')
ngrid[i][j] += 1;
if(inBounds(cr + 1, cc, r, c) && grid[cr + 1][cc] != '.')
ngrid[i][j] += 2;
if(inBounds(cr, cc + 1, r, c) && grid[cr][cc + 1] != '.')
ngrid[i][j] += 4;
if(inBounds(cr + 1, cc + 1, r, c) && grid[cr + 1][cc + 1] == '/')
ngrid[i][j] += 8;
cr++;
cc++;
}
}
int bound = (r + c - 1) / 2;
vector<vector<bool>> vis(bound, vector<bool>(bound, false));
int ans = 0;
for(int i = 0; i < bound; i++){
for(int j = 0; j < bound; j++){
if(!vis[i][j]){
ans += flood(ngrid, vis, i, j);
}
}
}
cout << ans << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3464kb
input:
2 2 /\ \/
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3464kb
input:
4 4 /\.. \.\. .\/\ ..\/
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3464kb
input:
2 2 \/ /\
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3528kb
input:
8 20 /\/\/\/\/\/\/\/\/\/\ \../\.\/./././\/\/\/ /./\.././\/\.\/\/\/\ \/\/\.\/\/./\/..\../ /\/./\/\/./..\/\/..\ \.\.././\.\/\/./\.\/ /.../\../..\/./.../\ \/\/\/\/\/\/\/\/\/\/
output:
26
result:
ok single line: '26'
Test #5:
score: 0
Accepted
time: 33ms
memory: 25928kb
input:
1000 1000 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
499001
result:
ok single line: '499001'
Test #6:
score: 0
Accepted
time: 29ms
memory: 26020kb
input:
1000 1000 \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...
output:
499000
result:
ok single line: '499000'
Test #7:
score: 0
Accepted
time: 47ms
memory: 25916kb
input:
1000 1000 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
122943
result:
ok single line: '122943'
Test #8:
score: 0
Accepted
time: 2ms
memory: 4412kb
input:
100 100 ................................................./\................................................. ................................................/..\................................................ .............................................../....\........................................
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 0ms
memory: 4472kb
input:
100 100 ................................................./\................................................. ................................................/..\................................................ ..............................................././\.\........................................
output:
25
result:
ok single line: '25'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
40 40 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\...
output:
760
result:
ok single line: '760'
Test #11:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
40 40 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/ /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\ \/\/\/\...
output:
760
result:
ok single line: '760'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3512kb
input:
21 21 /\/\/\/\/\/\/\/\/\/\. \...\...\...\...\...\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\.\.\.\.\.\.\.\ /././././././././././ \.\.\.\....
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 29ms
memory: 77924kb
input:
997 997 /\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
10 10 ..../\.... .../..\... .././\.\.. ././..\.\. /././\.\.\ \.\.\/././ .\.\.././. ..\.\/./.. ...\../... ....\/....
output:
3
result:
ok single line: '3'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3508kb
input:
10 11 ...../\.... ..../..\... ..././\.\.. .././..\.\. ./././\.\.\ .\.\.\/././ ..\.\.././. ...\.\/./.. ....\../... .....\/....
output:
3
result:
ok single line: '3'
Test #16:
score: 0
Accepted
time: 47ms
memory: 148788kb
input:
1000 1000 .....................................................................................................................................................................................................................................................................................................
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 0ms
memory: 4296kb
input:
100 100 ././././././././././././././././././././././././././././././././././././././././././././././././././ /./././././././././././././././././././././././././././././././././././././././././././././././././. ./././././././././././././././././././././././././././././././././././././././././././././...
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 2ms
memory: 4208kb
input:
100 100 .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\ \.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\. .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\...
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 1ms
memory: 4588kb
input:
100 100 .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\ ././././././././././././././././././././././././././././././././././././././././././././././././././ .\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\...
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
4 4 /\/\ \/\/ /\/\ \/\/
output:
5
result:
ok single line: '5'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3504kb
input:
3 3 /\. \/\ .\/
output:
2
result:
ok single line: '2'
Test #22:
score: 0
Accepted
time: 51ms
memory: 89876kb
input:
1000 1000 \/..\../..\/\/./......./..././..\../.../....\.\/././......./././.../..........\...\/.../..\.\../......\.....\.\/..\.././..\...\/...../.../\/./..\.......\../..\/\/..\/...../..././\/./..././................\....../..\....../././.../....\...\/....\.\/......\.......\../.../....\.\/..\....../.....
output:
86
result:
ok single line: '86'
Test #23:
score: 0
Accepted
time: 30ms
memory: 53444kb
input:
1000 500 /\.\...\/\...././....././\.\.....\.\/././\../......\...\.\.......\/././....\.././......./.../.../\.........\/....\../..\.....\........../\/\.....\/......./..\/......./........\.....\...\...\/./...../..\/......\..../.........../..\.\...././..........\/././\......../\/........\....../\...\../...
output:
722
result:
ok single line: '722'
Test #24:
score: 0
Accepted
time: 2ms
memory: 4348kb
input:
100 100 \/\/\/\/\/.../.../\/\.\/\.\/\/.../././\.\../././\........../..\/..././.../..\.\.......\/\..../\..../ /./\/\.\/...../.../\..../\../..\/.../..././.../..\...\../\/\.\../\/././..\/...../....././....\/././\ \/\.\...\/....\/.../......\/\.\.\...\/..\.\/\/..\../..\...\/\/\/./\../....\/\/./.../\/\../...
output:
184
result:
ok single line: '184'
Test #25:
score: 0
Accepted
time: 3ms
memory: 9460kb
input:
250 250 /\............/..\........../.../....././\....../....\.....\............................../.../.../..........\...\....../....\...\/........\.\/./...../..........\..../............\..../....\...\.......././....\.\................../...../..\.\/..\.\/\ ..\...\/...../\...\.......\.\.\/./\.\/......
output:
6
result:
ok single line: '6'
Test #26:
score: 0
Accepted
time: 24ms
memory: 46764kb
input:
500 1000 /\.\/\../....\/\.\/..././.../\/....\.././\/..\.\/..\/..\...\...\/....././....\.\.\.\.\.././\/./..\/.../..\/..\.\/./....\/./..\...\/..\/.../\..../..\/..\.\.\.....\/.../..\.\...\.\/........\/./..\...\/./...../\.\/././....\/..\/./\.\.\/././\/..\/./.../\...././..\/././...../\/\../..\/./\../.......
output:
2762
result:
ok single line: '2762'
Test #27:
score: 0
Accepted
time: 7ms
memory: 25240kb
input:
500 500 \...\../..\...\/...../\....../..\.....././....\/.../........\...\...\/./.../..././.../......\../\/....\...\../..\...\/..........\.././...../...../..\...\...\..../..\.\.....\/............\...\/\/..\.............\....../\/.../././\.....././.../............\..../\/./..\.\......../..\.....\../.....
output:
663
result:
ok single line: '663'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3752kb
input:
50 50 /\.\.\.\.././.../..././.../\.....\/..\/\.\...\.... ...../\.....\.\/./\/......./\..../..\/..\.\/./\../ ..../\.\/\..../..\.\../........\/....\.././\...\/\ \/\/././\...\/./\/........\.....\/\/./..\...\/\... ...\/...../\.........\/..\.\...\/.../.../\../..\.. \../....\../..\.././././\.\../...../......
output:
21
result:
ok single line: '21'