Pebbles
Pebbles
You’re given an unlimited number of pebbles to distribute across an NxN game board (N drawn from [3, 15]), where each square on the board contains some positive point value between 10 and 99, inclusive. A 6x6 board might look like this:
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 even diagonal neighbors. There’s no board wrap, so 44 and 61 of row three aren’t neighbors. Neither are 33 and 75 nor 55 and 92.
The goal is to maximize the number of points claimed by your placement of pebbles.
Write a program that reads in a sequence of boards from an input file and prints to stdout the maximum number of points attainable by an optimal pebble placement for each.
Giriş verilənləri
Each board is expressed as a series of lines, where each line is a space-delimited series of numbers. A blank line marks the end of each board (including the last one).
Çıxış verilənləri
Then your program would print the maximum number of points one can get by optimally distributing pebbles while respecting the two rules, which would be this (each output should be printed on a single line and followed with a newline).
Nümunə
71 24 95 56 54 85 50 74 94 28 92 96 23 71 10 23 61 31 30 46 64 33 32 95 89 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
572 683