Problem Statement
Manao is going to cut it into several non-overlapping fragments. Each of the fragments will be a horizontal or vertical strip containing 1 or more elements. A strip of length N can be interpreted as an N-digit number in base 10 by concatenating the digits on the strip in order. The horizontal strips are read from left to right and the vertical strips are read from top to bottom. The picture below shows a possible cutting of a 4x4 board:
Tutorial
A closer look at the input constraints will hint that it’s solvable using brute force approach. The maximum dimension of the rectangle is 4*4, and the total combination is \(2^{16}\) which fits within the time limit.
Code
public class CutTheNumbers {
public int maximumSum(String[] board) {
int R, C, T, res = 0;
R = board.length;
C = board[0].length();
T = R * C;
for (int i = 0; i < (1 << T); i++) {
int m = 0;
/* row count */
for (int r = 0; r < R; r++) {
int tmp = 0;
for (int c = 0; c < C; c++) {
int ith = (C * r + c);
if ((i & (1 << ith)) > 0) {
tmp = tmp * 10 + (board[r].charAt(c) - '0');
} else {
m += tmp;
tmp = 0;
}
}
m += tmp;
}
/* column count */
for (int c = 0; c < C; c++) {
int tmp = 0;
for (int r = 0; r < R; r++) {
int ith = (C * r + c);
if ((i & (1 << ith)) == 0) {
tmp = tmp * 10 + (board[r].charAt(c) - '0');
} else {
m += tmp;
tmp = 0;
}
}
m += tmp;
}
res = max(res, m);
}
return res;
}
}