QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134684#5730. Maze ConnectNicolas125841AC ✓51ms148788kbC++172.7kb2023-08-04 14:58:022023-08-04 14:58:03

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-04 14:58:03]
  • 评测
  • 测评结果:AC
  • 用时:51ms
  • 内存:148788kb
  • [2023-08-04 14:58:02]
  • 提交

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'