题目描述
Problem Description
Sudoku is a logic-based puzzle game where the player's task is to fill a $9\times9$ grid with digits $1\sim9$ such that the following conditions are met:
- Each digit from $1\sim9$ appears exactly once in each row.
- Each digit from $1\sim9$ appears exactly once in each column.
- The grid is divided into $9$ $3\times3$ subgrids, and each digit from $1\sim9$ appears exactly once in each subgrid.
You are given an incomplete Sudoku grid and need to determine if there are any errors. A grid is considered erroneous if and only if there exists a row, column, or subgrid where at least one digit appears two or more times.
The figure below shows a Sudoku grid without errors.
Input Format
The input consists of a $13\times13$ character matrix representing the Sudoku grid, where:
- Characters
-,|,+represent the grid framework, dividing the grid into $9$ $3\times3$ subgrids. - Character
.represents an empty cell. - Digits from $1\sim9$ represent filled cells.
Refer to the sample input for specifics.
Output Format
Output a single string. If the grid contains errors, output GRESKA; otherwise, output OK.
Sample Input and Output
Sample Input #1
+---+---+---+
|52.|...|.81|
|.39|58.|...|
|.8.|.9.|...|
+---+---+---+
|24.|...|1.3|
|1..|43.|86.|
|.63|..7|.24|
+---+---+---+
|...|1.9|35.|
|..8|.74|6..|
|31.|86.|7.9|
+---+---+---+
Sample Output #1
OK
Sample Input #2
+---+---+---+
|3..|6..|..4|
|4.9|8.1|..7|
|..7|.49|6..|
+---+---+---+
|946|157|8.2|
|.2.|3..|745|
|.7.|28.|...|
+---+---+---+
|...|4..|..5|
|8.5|.6.|.2.|
|734|..8|5..|
+---+---+---+
Sample Output #2
GRESKA
Sample Input #3
+---+---+---+
|5..|98.|67.|
|6..|...|.31|
|.2.|613|.4.|
+---+---+---+
|.96|8.2|1.7|
|.28|..5|.9.|
|7.3|19.|6..|
+---+---+---+
|962|.7.|.1.|
|1.5|...|76.|
|.7.|5..|9..|
+---+---+---+
Sample Output #3
GRESKA
Notes
Sample Explanation #1
This grid has no errors, so the output is OK.
Sample Explanation #2
The $9^{th}$ column has the digit $5$ appearing twice, and the bottom-right subgrid also has the digit $5$ appearing twice.
Sample Explanation #3
The $2^{nd}$ column has the digit $2$ appearing twice, and the $7^{th}$ column has the digit $6$ appearing twice.
Data Range
For $100\%$ of the data, the character matrix contains only digits $1\sim9$, characters -, |, +, ., and the positions of -, |, + are consistent with the sample.
This problem is group-tested.
| Subtask | Special Property | Points |
|---|---|---|
| $1$ | If there are errors, they can be found by checking only the row constraints | $11$ |
| $2$ | If there are errors, they can be found by checking only the column constraints | $12$ |
| $3$ | If there are errors, they can be found by checking only the subgrid constraints | $13$ |
| $4$ | No special properties | $14$ |
Notes
This problem's score is set according to the original COCI contest, with a full score of $50$.
The problem is translated from COCI2022-2023 CONTEST #1 T1 Sudoku.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分