Code: Select all
// http://acm.uva.es/p/v1/116.html
#include <iostream>
#include <climits>
using namespace std;
int rows; // 1 <= rows <= 10
int cols; // 1 <= cols <= 1000
const int max_rows = 12;
const int max_cols = 1020;
int in[max_rows][max_cols];
int next[max_rows][max_cols];
int sum[max_rows][max_cols];
int back[max_rows][max_cols];
void show_graph(int g[max_rows][max_cols]) {
for (int i = 1; i <= rows; ++i) {
for (int j = 1; j <= cols; ++j) {
cout << g[i][j] << '\t';
}
cout << '\n';
}
cout << '\n';
}
int wrap_row(int dir, int i) {
int selected_row = i + dir;
if (selected_row == 0) selected_row = rows;
if (selected_row > rows) selected_row = 1;
return selected_row;
}
void play() {
for (int i = 1; i <= rows; ++i) sum[i][cols] = in[i][cols];
for (int j = cols - 1; j > 0 ; --j) {
for (int i = 1; i <= rows; ++i) {
int best_sum=INT_MAX;
for (int dir = -1; dir <= 1; ++dir) {
int selected_row = wrap_row(dir, i);
int selected_sum = in[i][j] + sum[selected_row][j + 1];
if (selected_sum < best_sum) best_sum = selected_sum;
}
for (int dir = -1; dir <= 1; ++dir) {
int selected_row = wrap_row(dir, i);
int selected_sum = in[i][j] + sum[selected_row][j + 1];
if (selected_sum == best_sum) next[i][j] |= (1 << (dir + 1));
}
sum[i][j] = best_sum;
}
//show_graph(sum);
}
int min_sum = sum[1][1];
for (int i = 1; i <= rows; ++i)
if (sum[i][1] < min_sum) min_sum = sum[i][1];
/*show_graph(sum);
show_graph(next);
show_graph(back);
*/
int lex_best_row;
for (int i = 1; i <= rows; ++i)
if (sum[i][1] == min_sum) {
lex_best_row = i;
break;
}
if (cols == 1) {
cout << lex_best_row << '\n' << min_sum << '\n';
return;
}
for (int j = 1; j < cols; ++j) {
cout << lex_best_row;
int this_best_row = INT_MAX;
for (int dir = -1; dir <= 1; ++dir) {
if (next[lex_best_row][j] & (1 << (dir + 1))) {
int this_row = wrap_row(lex_best_row, dir);
if (this_row < this_best_row) this_best_row = this_row;
}
}
lex_best_row = this_best_row;
cout << ' ';
}
cout << lex_best_row << '\n';
//show_graph(sum);
cout << min_sum << '\n';
}
int main() {
while (cin >> rows >> cols) {
for (int i = 1; i <= rows; ++i) {
for (int j = 1 ; j <= cols; ++j) {
cin >> in[i][j];
back[i][j] = next[i][j] = 0;
}
}
play();
}
return 0;
}
.