11223번 - Magic Checkerboard 다국어

Consider an n × m checkerboard. On each cell of the checkerboard, place a positive integer. The values in each column of the checkerboard must be in strictly increasing order from top to bottom, and the values in each row of the checkerboard must be in strictly increasing order from left to right.

A Magic Checkerboard has an additional constraint. The cells that share only a corner must have numbers of different parity (Even vs Odd). Note that the following checkboard is invalid, because 2 and 4 share only a corner and have the same parity:

The first 4 × 4 example is a valid Magic Checkboard. Given a partially filled magic checkboard, can you fill the remaining locations on the checkboard, so that the sum of all values is as small as possible?

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each input starts with a line with two space-separated integers n and m (1 ≤ n, m ≤ 2 000), representing the number of rows (n) and the number of columns (m) of the checkerboard. Each of the next n lines will contain m space-separated integers c (0 ≤ c ≤ 2 000), representing the contents of the checkerboard. Zero is used for cells without numbers that you must fill in. You may use any positive integers to fill in the cells without numbers, so long as you form a valid Magic Checkerboard. You are not limited to numbers ≤ 2 000, and the numbers are not required to be unique.

Output a single integer representing the minimum sum possible by replacing the 0 cells with positive integers to form a valid Magic Checkerboard. Output −1 if it is not possible to replace the 0 cells to meet the constraints of a Magic Checkerboard.