Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 1.0 seconds
Cindy is playing a modified version of Sudoku. She has almost finished, but can’t quite figure out what the last number should be. Your job is the write a program that completes Cindy’s Sudoku game.
Sudoku is a numbers game, using the numbers 1 through 9, played on a 9x9 grid. Each number can only appear once in each column, once in each row, and once in a 3x3 grid.
In Cindy’s modified Sudoku, there are only two rules
- Each row can never contain the same number more than once, but it may contain any whole number from 1 to R inclusive in any order. R is the number of rows.
- Each column contains exactly one occurrence of all whole numbers 1 to R inclusive. The numbers could be in any order.
The grid of numbers will be R rows down and C columns across where R and C range from 1 to 42 inclusive. This means one of Cindy's grids might not have the same number of rows as columns.
Cindy will give you a valid board where one whole number is missing. There will be a lower-case
x character in place of this missing number. There will always be one, and only one,
x in a grid. Your program must print the board with the
x replaced by the missing number according to Cindy’s rules.
The first line has the whole numbers R and C separated by a space.
The next R lines each contain C numbers separated by spaces. Together these lines make up the R\times C grid.
1 \le R, C \le 42.
Print out the grid with the missing number filled in.
i.e. R lines each with C space separated whole numbers.
- Subtask 1 (20%): C=1, and the numbers are in ascending order (as in sample input 1). C=1 means there is only a single number (or the
x) on each line.
- Subtask 2 (20%): C=1, but the numbers may be in any order.
- Subtask 3 (60%): Full solution.
Sample Input 1
5 1 1 2 x 4 5
Sample Output 1
1 2 3 4 5
Sample Input 2
5 5 1 2 3 4 5 2 3 4 x 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4
Sample Output 2
1 2 3 4 5 2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4