C11CUT - Cắt bảng
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
int temp, res, a[5][5], used[5][5], m, n, step = 0;
void backtrack(int i, int j) {
if(j == n) {
if(i == m-1) { if(temp > res) res = temp; }
else backtrack(i+1, 0);
} else if(used[i][j]) backtrack(i, j+1);
else {
++step; used[i][j] = step; temp += a[i][j]; backtrack(i, j+1); temp -= a[i][j];
int x = a[i][j];
for(int c = j + 1; ; ++c) if(used[i][c]) {
for(int y = j + 1; y < c; ++y) used[i][y] = 0;
break;
} else {
x = x * 10 + a[i][c]; used[i][c] = step; temp += x;
backtrack(i, c+1); temp -= x;
}
x = a[i][j];
for(int r = i + 1; ; ++r) if(used[r][j]) {
for(int x = i + 1; x < r; ++x) used[x][j] = 0;
break;
} else {
x = x * 10 + a[r][j]; used[r][j] = step; temp += x;
backtrack(i, j+1); temp -= x;
}
used[i][j] = 0; --step;
}
}
int main() {
scanf("%d%d", &m, &n); for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j) scanf("%d", &a[i][j]);
for(int j = 0; j <= n; ++j) used[m][j] = 1; for(int i = 0; i <= m; ++i) used[i][n] = 1;
backtrack(0, 0);
printf("%d\n", res);
return 0;
}