You are given an unlimited number of pebbles to distribute across an
N × N game board (1 <= N <= 15), where each square on the board
contains an integer point value between 1 and 99, inclusive. The integers
on a given board may not be unique.
A 6 × 6 board might look like this:
78
78
11
55
20
11
98
54
81
43
39
97
12
15
79
99
58
10
13
79
83
65
34
17
85
59
61
12
58
97
40
63
97
85
66
90
The player distributes pebbles across the board so that:
·
At most one pebble resides in any given square.
·
No two pebbles are placed on adjacent squares.
Two squares are considered adjacent if they are horizontal, vertical,
or diagonal neighbors. There is no board wrap-in the above example,
55 and 85 are not neighbors, nor are 13 and 17.
The goal is to maximize the number of points claimed by
your placement of pebbles.
Input to your program will be a sequence of boards, terminated by end-of-file.
Each board will be separated
from the next by a blank line. Each board is a sequence of N lines consisting
of N integers separated from each other by whitespace.
For each board, your program is to print a line containing the maximum number
of points attainable. The result is to begin in the first column with no
leading zeroes or trailing whitespace.