QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#335408#5582. Chocolate Chip Fabricationmfshi03AC ✓403ms119224kbJava112.3kb2024-02-23 12:24:112024-02-23 12:24:11

Judging History

This is the latest submission verdict.

  • [2024-02-23 12:24:11]
  • Judged
  • Verdict: AC
  • Time: 403ms
  • Memory: 119224kb
  • [2024-02-23 12:24:11]
  • Submitted

answer


import java.io.*;
import java.util.*;


public class ChocolateChipFabrication {
    static class Point {
        int x, y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer str = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(str.nextToken());
        int m = Integer.parseInt(str.nextToken());

        char[][] padded = new char[n + 2][m + 2];
        for (char[] row : padded) {
            Arrays.fill(row, '-');
        }

        for (int i = 1; i <= n; i++) {
            String line = br.readLine();
            for (int j = 1; j <= m; j++) {
                padded[i][j] = line.charAt(j - 1);
            }
        }

        int[][] dp = new int[n + 2][m + 2];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        Queue<Point> queue = new LinkedList<>();
        for (int i = 0; i < n + 2; i++) {
            for (int j = 0; j < m + 2; j++) {
                if (padded[i][j] == '-') {
                    dp[i][j] = 0;
                    queue.add(new Point(i, j));
                }
            }
        }

        int cycles = 0;
        while (!queue.isEmpty()) {
            Point node = queue.poll();
            int i = node.x;
            int j = node.y;

            if (i - 1 >= 0 && dp[i - 1][j] == Integer.MAX_VALUE) {
                dp[i - 1][j] = dp[i][j] + 1;
                queue.add(new Point(i - 1, j));
            }

            if (j - 1 >= 0 && dp[i][j - 1] == Integer.MAX_VALUE) {
                dp[i][j - 1] = dp[i][j] + 1;
                queue.add(new Point(i, j - 1));
            }

            if (i + 1 < n + 2 && dp[i + 1][j] == Integer.MAX_VALUE) {
                dp[i + 1][j] = dp[i][j] + 1;
                queue.add(new Point(i + 1, j));
            }

            if (j + 1 < m + 2 && dp[i][j + 1] == Integer.MAX_VALUE) {
                dp[i][j + 1] = dp[i][j] + 1;
                queue.add(new Point(i, j + 1));
            }

            if (dp[i][j] > cycles) {
                cycles = dp[i][j];
            }
        }

        System.out.println(cycles);
    }

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 45ms
memory: 53316kb

input:

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

output:

2

result:

ok single line: '2'

Test #2:

score: 0
Accepted
time: 56ms
memory: 50308kb

input:

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

output:

1

result:

ok single line: '1'

Test #3:

score: 0
Accepted
time: 54ms
memory: 50052kb

input:

5 5
XXXXX
XXXXX
XXXXX
XXXXX
XXXXX

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 51ms
memory: 53848kb

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: 58ms
memory: 53284kb

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: 54ms
memory: 48700kb

input:

3 4
XXXX
-XXX
XXXX

output:

2

result:

ok single line: '2'

Test #7:

score: 0
Accepted
time: 49ms
memory: 49156kb

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: 49ms
memory: 49348kb

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: 51ms
memory: 49204kb

input:

1 1
X

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 47ms
memory: 48560kb

input:

3 3
XXX
XX-
XXX

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 51ms
memory: 52712kb

input:

2 3
XXX
XX-

output:

1

result:

ok single line: '1'

Test #12:

score: 0
Accepted
time: 52ms
memory: 48180kb

input:

3 1
-
-
X

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 61ms
memory: 53076kb

input:

2 2
XX
-X

output:

1

result:

ok single line: '1'

Test #14:

score: 0
Accepted
time: 60ms
memory: 52756kb

input:

2 2
--
-X

output:

1

result:

ok single line: '1'

Test #15:

score: 0
Accepted
time: 58ms
memory: 49176kb

input:

2 2
XX
XX

output:

1

result:

ok single line: '1'

Test #16:

score: 0
Accepted
time: 50ms
memory: 53012kb

input:

3 5
XXX-X
XXXXX
X-XXX

output:

2

result:

ok single line: '2'

Test #17:

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

input:

4 5
XXXXX
XXX-X
X-XXX
XXXXX

output:

1

result:

ok single line: '1'

Test #18:

score: 0
Accepted
time: 326ms
memory: 93196kb

input:

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

output:

337

result:

ok single line: '337'

Test #19:

score: 0
Accepted
time: 310ms
memory: 92196kb

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: 387ms
memory: 115936kb

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: 347ms
memory: 98196kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

15

result:

ok single line: '15'

Test #22:

score: 0
Accepted
time: 358ms
memory: 111088kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

7

result:

ok single line: '7'

Test #23:

score: 0
Accepted
time: 361ms
memory: 109328kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

4

result:

ok single line: '4'

Test #24:

score: 0
Accepted
time: 357ms
memory: 108104kb

input:

999 999
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

2

result:

ok single line: '2'

Test #25:

score: 0
Accepted
time: 341ms
memory: 119224kb

input:

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

output:

2

result:

ok single line: '2'

Test #26:

score: 0
Accepted
time: 403ms
memory: 118368kb

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: 391ms
memory: 116676kb

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: 327ms
memory: 89660kb

input:

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

output:

381

result:

ok single line: '381'

Test #29:

score: 0
Accepted
time: 370ms
memory: 105348kb

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: 0
Accepted
time: 317ms
memory: 92424kb

input:

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

output:

155

result:

ok single line: '155'

Test #31:

score: 0
Accepted
time: 384ms
memory: 89576kb

input:

999 999
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------...

output:

499

result:

ok single line: '499'

Test #32:

score: 0
Accepted
time: 372ms
memory: 113132kb

input:

999 999
X-XXX-XXX-XXX-X-X-XXX-X-XXXXXXX-XXX-XXXXXXX-XXX-XXXXXXX-X-XXXXX-XXX-X-XXXXXXX-XXXXX-X-XXX-XXX-XXXXX-XXXXXXXXX-X-X-XXXXXXX-XXX-XXXXXXXXX-XXX-XXXXXXXXXXX-XXX-X-XXXXXXXXX-X-XXX-XXX-XXXXXXXXXXXXXXX-XXX-XXX-X-X-X-XXXXXXXXX-XXX-X-XXXXX-XXX-X-XXXXX-XXXXXXX-XXXXXXX-XXXXXXX-XXX-X-XXX-XXXXXXXXXXX-X-X-...

output:

2

result:

ok single line: '2'

Test #33:

score: 0
Accepted
time: 400ms
memory: 113876kb

input:

999 999
XXXXX-XXXXX-X-X-X-XXXXXXXXXXX-XXX-XXX-X-XXXXXXX-X-XXXXX-XXXXXXXXX-XXXXXXX-XXX-X-X-XXX-X-XXX-XXXXX-XXX-X-X-XXX-XXX-X-XXX-XXXXXXX-XXXXX-XXXXXXXXX-XXX-XXXXXXXXXXXXXXX-XXX-X-X-XXXXX-X-X-XXXXX-XXXXX-XXXXXXXXXXXXX-XXXXXXX-XXX-XXX-XXX-X-X-XXXXXXX-XXXXXXX-XXXXXXX-XXXXX-X-XXXXXXX-X-X-XXX-XXXXXXXXX-X-...

output:

2

result:

ok single line: '2'

Test #34:

score: 0
Accepted
time: 383ms
memory: 104868kb

input:

1000 1000
XXXXX-XX-XXX-X-XXX-XXXXXXXXXXXXXXXXX-XXXXXX-XXXXXXXXXXXXX-XXXXXXX-XXXXXXXXXXXXXXX-XXXXXX-XX-XXXXXXXXXXXXXXXXXX-XXXXXX-XXXXXXXXXXX-XXXXXXXXXXXXXXXXX-X-XXXXXX-XXXXXXXXXXXXXXXXXXXXXX-XXXXXXX-XX-XXXX-XXXXXXXXXXXXXXXX-XXX-XXXXX-XXX-XXXX-XXXXXXXXXXXXXXXXXXXXXXXX-XXXXX-XXX-XXXXXX-XXX-XXXXXXXXXXXX...

output:

8

result:

ok single line: '8'

Test #35:

score: 0
Accepted
time: 381ms
memory: 117300kb

input:

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

output:

3

result:

ok single line: '3'

Test #36:

score: 0
Accepted
time: 368ms
memory: 116696kb

input:

1000 1000
X---X------------X--X-----X----------X-----------------------------------------------------------X--X---X---X-------X---X-----------------------XX-----------------X-----X----XX---------------------------X------XX---------X-----------------X--------X--------------X---X-----X----------------...

output:

2

result:

ok single line: '2'

Test #37:

score: 0
Accepted
time: 294ms
memory: 89432kb

input:

1000 1000
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX...

output:

500

result:

ok single line: '500'