find max important neighbours

find max important neighbours

We have a rectangle with n rows and m columns filled with numbers from 1
to n*m. Cell (i,j) of the rectangle is important iff: * i = 1 and j = 1
(or) *there is an important cell (a,b) such that (a,b) is a neighbor of
(i,j) and the number on (i,j) is greater than number on cell (a,b) and all
of (a,b)'s neighbors except for ( (i,j) itself
Two cells are considered to be neighbors if they share a common edge
between them. Unfortunately the number in some of the cells has been
erased. We want to write a number to those cells such that the resultant
rectangle has all the numbers between 1 to n*m and it contains as many
important cells as possible. In case there are several ways to do that, we
are interested with the rectangle which is lexicographically smallest. A
table is lexicographically smaller that the other if the string of its
row-major view is lexicographically smaller than the other. Input: The
first line of the input contains two integers n and m, Each of the next n
lines contains m tokens. Each token is either an integer between 1 and n*m
or '?'. Output: Print the maximum number of important cells that can be
obtained in the first line of the output and print the rectangle in the
next n lines.
Constraints: 1 <=n,m <=6
Sample input #00: 2 3 2 ? ? ? ? 3
Sample output #00: 3 2 1 4 5 6 3
Sample input #01: 6 6 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
? ? ? ? ? ? ? ? ? ?
Sample output #02: 24 1 2 3 13 14 15 4 6 8 10 11 16 5 7 9 12 19 17 28 26
24 22 20 18 29 27 25 23 21 36 30 31 32 33 34 35