QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#847334#5730. Maze ConnectTeapot#AC ✓173ms6336kbC++202.8kb2025-01-07 20:34:222025-01-07 20:34:23

Judging History

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

  • [2025-01-07 20:34:23]
  • 评测
  • 测评结果:AC
  • 用时:173ms
  • 内存:6336kb
  • [2025-01-07 20:34:22]
  • 提交

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

int res,r,c;

void bfs(int i, int j, vector<vector<bool>>& ar,vector<vector<bool>>& vis)
{
    queue<pii> que;
    que.push({i,j});
    vis[i][j] = 1;
    bool t = false;
    while(!que.empty())
    {
        pii cur = que.front();
        que.pop();
        i = cur.x;
        j = cur.y;
        if(i == 0 || i == 3*r-1)
            t = true;
        if(j == 0 || j == 3*c-1)
            t = true;
        if(i > 0 && ar[i-1][j] == 0 && vis[i-1][j] == 0)
        {
            que.push({i-1,j});
            vis[i-1][j] = 1;
        }
        if(i < 3*r-1 && ar[i+1][j] == 0 && vis[i+1][j] == 0)
        {
            que.push({i+1,j});
            vis[i+1][j] = 1;
        }
        if(j > 0 && ar[i][j-1] == 0 && vis[i][j-1] == 0)
        {
            que.push({i,j-1});
            vis[i][j-1] = 1;
        }
        if(j < 3*c-1 && ar[i][j+1] == 0 && vis[i][j+1] == 0)
        {
            que.push({i,j+1});
            vis[i][j+1] = 1;
        }
    }
    if(!t)
        res++;
}

int32_t main()
{
    res = 0;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> r >> c;
    vector<vector<bool>> ar(3*r,vector<bool>(3*c,0));
    vector<vector<bool>> vis(3*r,vector<bool>(3*c,0));
    FOR(i,0,r)
    {
        string s;
        cin >> s;
        FOR(j,0,c)
        {
            if(s[j] == '\\')
            {
                ar[3*i][3*j] = 1;
                ar[3*i+1][3*j+1] = 1;
                ar[3*i+2][3*j+2] = 1;
            }
            else if(s[j] == '/')
            {
                ar[3*i+2][3*j] = 1;
                ar[3*i+1][3*j+1] = 1;
                ar[3*i][3*j+2] = 1;
            }
        }
    }
    FOR(i,0,3*r)
        FOR(j,0,3*c)
        {
            if(ar[i][j] == 0 && vis[i][j] == 0)
                bfs(i,j,ar,vis);
        }
    cout << res;
}

详细

Test #1:

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

input:

2 2
/\
\/

output:

1

result:

ok single line: '1'

Test #2:

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

input:

4 4
/\..
\.\.
.\/\
..\/

output:

2

result:

ok single line: '2'

Test #3:

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

input:

2 2
\/
/\

output:

0

result:

ok single line: '0'

Test #4:

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

input:

8 20
/\/\/\/\/\/\/\/\/\/\
\../\.\/./././\/\/\/
/./\.././\/\.\/\/\/\
\/\/\.\/\/./\/..\../
/\/./\/\/./..\/\/..\
\.\.././\.\/\/./\.\/
/.../\../..\/./.../\
\/\/\/\/\/\/\/\/\/\/

output:

26

result:

ok single line: '26'

Test #5:

score: 0
Accepted
time: 104ms
memory: 6336kb

input:

1000 1000
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...

output:

499001

result:

ok single line: '499001'

Test #6:

score: 0
Accepted
time: 103ms
memory: 6076kb

input:

1000 1000
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/...

output:

499000

result:

ok single line: '499000'

Test #7:

score: 0
Accepted
time: 149ms
memory: 6192kb

input:

1000 1000
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...

output:

122943

result:

ok single line: '122943'

Test #8:

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

input:

100 100
................................................./\.................................................
................................................/..\................................................
.............................................../....\........................................

output:

1

result:

ok single line: '1'

Test #9:

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

input:

100 100
................................................./\.................................................
................................................/..\................................................
..............................................././\.\........................................

output:

25

result:

ok single line: '25'

Test #10:

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

input:

40 40
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\...

output:

760

result:

ok single line: '760'

Test #11:

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

input:

40 40
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\
\/\/\/\...

output:

760

result:

ok single line: '760'

Test #12:

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

input:

21 21
/\/\/\/\/\/\/\/\/\/\.
\...\...\...\...\...\
/././././././././././
\.\.\.\.\.\.\.\.\.\.\
/././././././././././
\.\.\.\.\.\.\.\.\.\.\
/././././././././././
\.\.\.\.\.\.\.\.\.\.\
/././././././././././
\.\.\.\.\.\.\.\.\.\.\
/././././././././././
\.\.\.\.\.\.\.\.\.\.\
/././././././././././
\.\.\.\....

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 102ms
memory: 6064kb

input:

997 997
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\...

output:

1

result:

ok single line: '1'

Test #14:

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

input:

10 10
..../\....
.../..\...
.././\.\..
././..\.\.
/././\.\.\
\.\.\/././
.\.\.././.
..\.\/./..
...\../...
....\/....

output:

3

result:

ok single line: '3'

Test #15:

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

input:

10 11
...../\....
..../..\...
..././\.\..
.././..\.\.
./././\.\.\
.\.\.\/././
..\.\.././.
...\.\/./..
....\../...
.....\/....

output:

3

result:

ok single line: '3'

Test #16:

score: 0
Accepted
time: 126ms
memory: 6320kb

input:

1000 1000
.....................................................................................................................................................................................................................................................................................................

output:

0

result:

ok single line: '0'

Test #17:

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

input:

100 100
././././././././././././././././././././././././././././././././././././././././././././././././././
/./././././././././././././././././././././././././././././././././././././././././././././././././.
./././././././././././././././././././././././././././././././././././././././././././././...

output:

0

result:

ok single line: '0'

Test #18:

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

input:

100 100
.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\
\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.
.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\...

output:

0

result:

ok single line: '0'

Test #19:

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

input:

100 100
.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\
././././././././././././././././././././././././././././././././././././././././././././././././././
.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\.\...

output:

0

result:

ok single line: '0'

Test #20:

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

input:

4 4
/\/\
\/\/
/\/\
\/\/

output:

5

result:

ok single line: '5'

Test #21:

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

input:

3 3
/\.
\/\
.\/

output:

2

result:

ok single line: '2'

Test #22:

score: 0
Accepted
time: 173ms
memory: 6104kb

input:

1000 1000
\/..\../..\/\/./......./..././..\../.../....\.\/././......./././.../..........\...\/.../..\.\../......\.....\.\/..\.././..\...\/...../.../\/./..\.......\../..\/\/..\/...../..././\/./..././................\....../..\....../././.../....\...\/....\.\/......\.......\../.../....\.\/..\....../.....

output:

86

result:

ok single line: '86'

Test #23:

score: 0
Accepted
time: 88ms
memory: 5052kb

input:

1000 500
/\.\...\/\...././....././\.\.....\.\/././\../......\...\.\.......\/././....\.././......./.../.../\.........\/....\../..\.....\........../\/\.....\/......./..\/......./........\.....\...\...\/./...../..\/......\..../.........../..\.\...././..........\/././\......../\/........\....../\...\../...

output:

722

result:

ok single line: '722'

Test #24:

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

input:

100 100
\/\/\/\/\/.../.../\/\.\/\.\/\/.../././\.\../././\........../..\/..././.../..\.\.......\/\..../\..../
/./\/\.\/...../.../\..../\../..\/.../..././.../..\...\../\/\.\../\/././..\/...../....././....\/././\
\/\.\...\/....\/.../......\/\.\.\...\/..\.\/\/..\../..\...\/\/\/./\../....\/\/./.../\/\../...

output:

184

result:

ok single line: '184'

Test #25:

score: 0
Accepted
time: 11ms
memory: 4012kb

input:

250 250
/\............/..\........../.../....././\....../....\.....\............................../.../.../..........\...\....../....\...\/........\.\/./...../..........\..../............\..../....\...\.......././....\.\................../...../..\.\/..\.\/\
..\...\/...../\...\.......\.\.\/./\.\/......

output:

6

result:

ok single line: '6'

Test #26:

score: 0
Accepted
time: 87ms
memory: 4872kb

input:

500 1000
/\.\/\../....\/\.\/..././.../\/....\.././\/..\.\/..\/..\...\...\/....././....\.\.\.\.\.././\/./..\/.../..\/..\.\/./....\/./..\...\/..\/.../\..../..\/..\.\.\.....\/.../..\.\...\.\/........\/./..\...\/./...../\.\/././....\/..\/./\.\.\/././\/..\/./.../\...././..\/././...../\/\../..\/./\../.......

output:

2762

result:

ok single line: '2762'

Test #27:

score: 0
Accepted
time: 44ms
memory: 4564kb

input:

500 500
\...\../..\...\/...../\....../..\.....././....\/.../........\...\...\/./.../..././.../......\../\/....\...\../..\...\/..........\.././...../...../..\...\...\..../..\.\.....\/............\...\/\/..\.............\....../\/.../././\.....././.../............\..../\/./..\.\......../..\.....\../.....

output:

663

result:

ok single line: '663'

Test #28:

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

input:

50 50
/\.\.\.\.././.../..././.../\.....\/..\/\.\...\....
...../\.....\.\/./\/......./\..../..\/..\.\/./\../
..../\.\/\..../..\.\../........\/....\.././\...\/\
\/\/././\...\/./\/........\.....\/\/./..\...\/\...
...\/...../\.........\/..\.\...\/.../.../\../..\..
\../....\../..\.././././\.\../...../......

output:

21

result:

ok single line: '21'