QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#688233#5582. Chocolate Chip FabricationTenshi#WA 670ms32144kbC++231.2kb2024-10-30 01:18:302024-10-30 01:18:31

Judging History

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

  • [2024-10-30 01:18:31]
  • 评测
  • 测评结果:WA
  • 用时:670ms
  • 内存:32144kb
  • [2024-10-30 01:18:30]
  • 提交

answer

#include <bits/stdc++.h>
#include <iostream>
#include <queue>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)

#define sz(x) (long long)(x).size()

int main() {
    int n, m; cin >> n >> m;
    vector<vector<bool>> grid(n+2, vector<bool>(m+2, false));
    rep(i, n) {
        string s; cin >> s;
        rep (j, m) {
            if (s[j]=='X') grid[i+1][j+1] = true;
        }
    }

    priority_queue<pair<int, pair<int, int>>> pq;

    pq.push({0, {0, 0}});

    vector<vector<int>> dist(n+2, vector<int>(m+2, -1));


    while (sz(pq)) {
        pair<int, pair<int, int>> data = pq.top();pq.pop();

        int depth = -data.first;
        int r = data.second.first;
        int c = data.second.second;
        if (dist[r][c]!=-1) continue;
        dist[r][c] = depth;
        pair<int, int> disp[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        for (pair<int, int> off : disp) {
            if (r + off.first < 0 or r+off.first >= n+2 or c + off.second < 0 or c+off.second >= m+2) continue;
            pq.push({(grid[r + off.first][c + off.second] ? -depth-1:0), {r+off.first, c+off.second}});
        }
    }
    int mx = 0;
    rep(i, n+2) {rep(j, m+2) {mx = max(mx, dist[i][j]); }}
    cout << mx << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3764kb

input:

5 5
-X-X-
XXXXX
XXXXX
-XXX-
--X--

output:

2

result:

ok single line: '2'

Test #2:

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

input:

4 5
--XXX
--X-X
X-XXX
XX---

output:

1

result:

ok single line: '1'

Test #3:

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

input:

5 5
XXXXX
XXXXX
XXXXX
XXXXX
XXXXX

output:

3

result:

ok single line: '3'

Test #4:

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

input:

9 9
----X----
----X----
----X----
---XXX---
XXXXXXXXX
---XXX---
----X----
----X----
----X----

output:

3

result:

ok single line: '3'

Test #5:

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

input:

7 7
--X-X--
--X-X--
XXXXXXX
--X-X--
XXXXXXX
--X-X--
--X-X--

output:

2

result:

ok single line: '2'

Test #6:

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

input:

3 4
XXXX
-XXX
XXXX

output:

2

result:

ok single line: '2'

Test #7:

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

input:

10 10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

output:

5

result:

ok single line: '5'

Test #8:

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

input:

10 10
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXX-XXXXX
XXXXXXXXXX
XXXXXXXXXX
XXXXXXXXXX

output:

4

result:

ok single line: '4'

Test #9:

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

input:

1 1
X

output:

1

result:

ok single line: '1'

Test #10:

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

input:

3 3
XXX
XX-
XXX

output:

1

result:

ok single line: '1'

Test #11:

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

input:

2 3
XXX
XX-

output:

1

result:

ok single line: '1'

Test #12:

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

input:

3 1
-
-
X

output:

1

result:

ok single line: '1'

Test #13:

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

input:

2 2
XX
-X

output:

1

result:

ok single line: '1'

Test #14:

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

input:

2 2
--
-X

output:

1

result:

ok single line: '1'

Test #15:

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

input:

2 2
XX
XX

output:

1

result:

ok single line: '1'

Test #16:

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

input:

3 5
XXX-X
XXXXX
X-XXX

output:

2

result:

ok single line: '2'

Test #17:

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

input:

4 5
XXXXX
XXX-X
X-XXX
XXXXX

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 495ms
memory: 8288kb

input:

1000 1000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

337

result:

ok single line: '337'

Test #19:

score: 0
Accepted
time: 632ms
memory: 14636kb

input:

1000 1000
-XXX-XXXXXXXXXXXXXXXXXX--XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXX-XXXXXXXXXXX-XXXXXX-XXXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXX-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX-XXXXXXXXXXXXXXXXXXXX-XXXXXXXXX-XXXXXXXXXX-XX...

output:

38

result:

ok single line: '38'

Test #20:

score: 0
Accepted
time: 588ms
memory: 15024kb

input:

1000 1000
X--X--XX--X--X---X-XXX---X----X-X-----X-X--X--XX--X----X--X--XX----X-XXX-----X-XXX-X-XX------X-X-X--XXX-X-XX--X-X----XXX-X--XX-X-X-X-XXXXXX-X-----X-X--XXX---X--XXX-X-X-XX----XX-----X-X-XX-X-X--X-X--X-X--X-X----X-X------X--XXXXX---XXXXXX-XX--X-XX-XXXXX-XXXX-X-X--XX---X-X----XXXX-XX---XXX--X...

output:

5

result:

ok single line: '5'

Test #21:

score: 0
Accepted
time: 557ms
memory: 11436kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

15

result:

ok single line: '15'

Test #22:

score: 0
Accepted
time: 670ms
memory: 20436kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

7

result:

ok single line: '7'

Test #23:

score: 0
Accepted
time: 619ms
memory: 32144kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4

result:

ok single line: '4'

Test #24:

score: 0
Accepted
time: 507ms
memory: 20688kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

2

result:

ok single line: '2'

Test #25:

score: 0
Accepted
time: 420ms
memory: 9008kb

input:

1000 1000
--------------------------------------------------------------------------------------------------------------------X-------X-----------------------------------------------------------------X--------------------------XXX--------------------------------------------------X-------------------...

output:

2

result:

ok single line: '2'

Test #26:

score: 0
Accepted
time: 651ms
memory: 20520kb

input:

1000 1000
XXXX-------------XXX----------XXX--XXX----------X--X----XXXX-XXXXX---------XXXX----------X--------------X-------------X--------X--X-------------X------XXX--X-XXXXXX-XXX------X---------XXX-X-----XXXXXXX--XX----X------X------XXX-------------X-----X----------------XXXXX-XXXXXXX-XXXX-X-X------...

output:

4

result:

ok single line: '4'

Test #27:

score: 0
Accepted
time: 555ms
memory: 14672kb

input:

1000 1000
-----------XXXXXXXXX----XXXXXXX-----------------------------------XXXXXXX-----------------------------------------XXXXXXX-----X-----------XXXXX-XXXXXXXXXXXXXXX------------------XXXXXXXX--XXXXX---------------XXXXXXXXXXXXXX--------XXXXXXXXXXXXXXXX----------------------------XXXXX----XXXXXXX-...

output:

11

result:

ok single line: '11'

Test #28:

score: 0
Accepted
time: 386ms
memory: 8088kb

input:

1000 1000
----------------------------------------------------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

381

result:

ok single line: '381'

Test #29:

score: 0
Accepted
time: 645ms
memory: 20776kb

input:

1000 1000
----------X--XXXXXXXXXXXXXXX------XXXXXXXXXXXXXXXXXXXX----------------XXX--XXX--X------XXXX-X------------------XXXXXXX-----------XXX--X----------XXX--------------------XXXXX-----------------------X---X---------XXXXX-----------XXXXXXXXXXXXXXX--------XXXXXXXXX----------XXXXXXX---------------...

output:

10

result:

ok single line: '10'

Test #30:

score: -100
Wrong Answer
time: 478ms
memory: 8060kb

input:

1000 1000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX--------------XXXXXXXXXXX----------------------------------------------------------------------------------------------------------XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

163

result:

wrong answer 1st lines differ - expected: '155', found: '163'