Combination Lock
Time limit1sMemory limit512 MB
A grid of digits can be rotated one step at a time; find the minimum total rotations so that the cells showing some digit m form an L shape (a vertical arm and a horizontal arm meeting at a corner).
- Level
Medium7 of 10
- Topics
- Prefix sum, Brute force, Implementation, Array
- Solved
- No attempts yet
Problem
Gael has a padlock with a combination lock. Unlike a typical combination lock, which has several rotating discs (one per digit) from left to right, Gael's combination lock has R × C rotating discs arranged in R rows (numbered 1 to R) and C columns (numbered 1 to C). For convenience, the rotating disc in the i-th row and j-th column is denoted as rotating disc (i, j).
As in a typical combination lock, each rotating disc in Gael's lock has 10 symbols numbered 0 to 9, and one of them is visible to Gael at any moment.
In one operation, Gael can choose one of the R × C rotating discs and rotate it 1/10 turn clockwise. The visible symbol then increases by 1 if the previously visible symbol is not 9, or becomes 0 if it was 9.
In a typical combination lock, opening the lock requires rotating each disc by exactly the right amount so that it shows a predetermined symbol. Gael's lock, however, is mechanically magical and behaves differently.
Gael's lock opens when the set of rotating discs currently showing some symbol m forms the letter L. Formally, the lock opens if there exist a symbol m and integers x, y, δx, δy (0 ≤ m ≤ 9; 1 ≤ x − δx < x ≤ R; 1 ≤ y < y + δy ≤ C) such that rotating disc (i, j) shows symbol m if and only if at least one of the following holds.
- i = x and y ≤ j ≤ y + δy
- x − δx ≤ i ≤ x and j = y
Currently, rotating disc (i, j) shows symbol Si,j. Help Gael determine the minimum number of operations needed to open his lock.
Input
The input begins with a line containing two integers R C (2 ≤ R, C ≤ 1000), the number of rows and columns in Gael's combination lock. The next R lines each contain a string Si of C characters between 0 and 9, representing the symbols currently visible on the rotating discs. The j-th character on the i-th line is the value of Si,j.
Output
Output one line with an integer, the minimum number of operations needed to open Gael's lock.