I was asked an interesting problem on an university interview. (I won't tell you what university it was.) However, I couldn't come up with an effective solution. I would appreciate if anyone has any thoughts or approaches!
Statement
You are given two integers x
y
, and a n
by n
chessboard, each square is given either black, white, or red. (Denoted by 0,1,2) You also have an infinite amount of black, white, and red chess pieces. You are to put exactly one piece on each of the squares. You have to calculate the maximum score possible. The score is calculated as follows:
- For each square, if the color of the square is same as the color of the piece, you get
x
points. - For each unordered pair of squares that are adjacent (up, down, left, right) if the color of the chess pieces are the same, you get
y
points.
Constraints
$$$n \le 100$$$ $$$x,y \le 10^9$$$
Sample Input
n=3 x=4 y=2
110
001
100
Sample Output
46
Explanation:
We can put the chess pieces as follows:
110
000
000
This way we have 7 chess pieces that have the same color as the square color, giving us 7x4=28
points. We also have 1 pair of white and 8 pairs of black pieces that are adjacent, giving us 9x2=18
points. Total is 46
.