Collecting Gems (APCS 2024-10 Intermediate)

Points 100 1.0s 256M

There is an \(M \times N\) map. Each cell stores one integer:

  • \(-1\) denotes a wall that the robot cannot enter.
  • Any other value is the current number of gems in that cell.

The robot starts at \((r,c)\) facing right. It maintains a variable score, whose initial value is \(0\). Rows are numbered from \(0\) to \(M-1\) from top to bottom, and columns are numbered from \(0\) to \(N-1\) from left to right.

The robot repeatedly performs the following steps in order:

  1. If the current cell contains \(0\) gems, stop immediately.
  2. Add the number of gems in the current cell before picking one up to score, then remove one gem from the cell.
  3. If score is a multiple of \(k\), turn right by \(90^\circ\).
  4. If the cell in front is a wall or outside the map, keep turning right by \(90^\circ\) until the cell in front can be entered.
  5. Move forward by one cell and return to step 1.

The following diagram summarizes one iteration. Successive right turns face right, down, left, and up.

Flowchart showing that each robot iteration checks for zero gems, adds the current amount to the score, picks one gem, turns according to the score, avoids walls, and moves

Output the total number of gems removed before the robot stops.

Input

The first line contains five integers \(M,N,k,r,c\).

The next \(M\) lines each contain \(N\) integers, describing the rows of the map from top to bottom.

Constraints

  • \(1 \le M \le 100\)
  • \(2 \le N \le 100\)
  • \(1 \le k \le 20\)
  • \(0 \le r < M\)
  • \(0 \le c < N\)
  • Every cell value is either \(-1\) or an integer between \(0\) and \(k-1\).
  • The starting cell \((r,c)\) is not a wall.
  • The four neighbors of the starting cell are not all walls or outside the map.
  • The robot is guaranteed to stop eventually.

Output

Output one integer: the total number of gems collected by the robot.

Scoring

There are two subtasks:

Subtask Points Additional constraint
1 60 \(M=1\)
2 40 No additional constraints

When \(M=1\), a score-triggered right turn must be followed by one more right turn before the robot faces another cell in the same row. Therefore, its overall effect is a U-turn.

Sample Input 1

1 7 3 0 4
1 -1 2 1 2 1 0

Sample Output 1

5

Sample Explanation 1

The one-row map and path for sample one; the robot checks columns 4, 5, 4, 3, 2, and 3, where it stops on zero gems

The robot checks the cells \((0,4),(0,5),(0,4),(0,3),(0,2),(0,3)\) in this order. When it returns to \((0,3)\) for the last time, the only gem there has already been removed, so the robot stops after collecting \(5\) gems.

Sample Input 2

4 5 4 2 1
2 0 1 1 1
2 -1 0 2 -1
0 3 2 3 0
-1 1 -1 3 0

Sample Output 2

8

Sample Explanation 2

The map and eight gem-collection steps for sample two; arrows show the movement order, wall turns, and final stopping cell

Circled labels \(1\) through \(8\) mark the cells where gems are collected. S is the starting cell, and E is the cell with \(0\) gems where the robot stops. A cell may be visited more than once, and its gem count decreases whenever a gem is collected there.

Source

2024 October APCS Programming Practice, Problem 2: ZeroJudge o712, Collecting Gems. The presentation also refers to Yi-Zhe Wang's HackMD solution; constraints and samples follow the official APCS Intermediate sample booklet.

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.