Moving (APCS 2023-10 Advanced)

Points 100 1.0s 256M

Moving

The Teenage Mutant Ninja Turtles live in the sewers and are preparing to move. The sewer system is represented by an \(n\times m\) matrix. Each character indicates the directions in which the pipe in that cell is open.

Two vertically or horizontally adjacent pipes are connected if both pipes have openings facing each other. Pipes that can reach one another through a sequence of connections belong to the same connected component. Find the number of pipes in the largest connected component.

The characters and their opening directions are:

Character Open directions
F right and down
H left and right
7 left and down
I up and down
X up, down, left, and right
L right and up
J left and up
0 no pipe

Pipe shapes

Input Format

The first line contains two space-separated integers \(n\) and \(m\), the number of rows and columns of the matrix.

Each of the next \(n\) lines contains a string of length \(m\) describing the sewer. Every character is one of F, H, 7, I, X, L, J, and 0.

Output Format

Output one integer: the number of pipes in the largest connected component. If the matrix contains no pipes, output \(0\).

Constraints

  • \(1\le n,m\le 500\)
  • The time limit for each test case is 1 second.
  • There are 20 scored test cases, each worth 5 points. The score is awarded per correctly passed test case.

Subtasks

Subtask Points Additional constraints
1 60 The sewer contains no X
2 40 No additional constraints

Sample Input 1

3 4
FHH7
IIII
LHHJ

Sample Output 1

10

Sample Input 2

4 7
0F70000
FXJ0000
II700X7
LJ0HHLJ

Sample Output 2

9

Sample Explanation

Sample 1:

Pipe connections in sample 1

Sample 2:

Pipe connections in sample 2

Source

APCS October 2023 Programming Problem 3, "Moving," also available as ZeroJudge m372.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.