#include<bits/stdc++.h>
using namespace std;
const int inf = 1e9, B = 301;
int n, m, a[90001], ans[90001], dt[90001][605];
bool f;
bool valid (int X, int Y) {
if(!(1 <= X && X <= n*m && B-n <= Y && Y <= B+n)) return false;
if(!(1 <= X+Y-B && X+Y-B <= n*m)) return false;
return true;
}
void track (int X, int Y) {
if(X == 1 && Y == B) return;
int i, j;
ans[X] = 1; ans[X+Y-B] = 1;
i = X - n, j = Y + n;
if(valid(i, j) && i+n <= n*m && j-n >= B-n && dt[i][j] + (j-n != B)*a[i+n] == dt[X][Y]) {
track(i, j); return;
}
i = X-1, j = Y+1;
if(valid(i, j) && i%n && j-1 >= B-n && dt[i][j] + (j-1 != B)*a[i+1] == dt[X][Y]) {
track(i, j); return;
}
i = X, j = Y-m;
if(valid(i, j) && j+m <= B+n && i+j+m-B <= n*m && dt[i][j] + (j+m != B)*a[i+j+m-B] == dt[X][Y]) {
track(i, j); return;
}
i = X, j = Y-1;
if(valid(i, j) && j+1 <= B+n && i+j+1-B <= n*m && dt[i][j] + (j+1 != B)*a[i+j+1-B] == dt[X][Y]) {
track(i, j); return;
}
}
int main()
{
scanf("%d%d",&n,&m);
if(n < m) {swap(n, m); f = true;}
for(int i=1;i<=n*m;i++) {
scanf("%d",&a[i]);
for(int j=B-n-1;j<=B+n+1;j++) {
dt[i][j] = inf;
}
}
dt[1][B] = a[1];
for(int i=1;i<=n*m;i++) {
for(int j=B-n;j<=B+n;j++) {
if(i+j-B < 1 || i+j-B > n*m) continue;
if(i+n <= n*m && j-n >= B-n) {
dt[i+n][j-n] = min(dt[i+n][j-n], dt[i][j] + (j-n != B)*a[i+n]);
}
if(i%n && j-1 >= B-n) {
dt[i+1][j-1] = min(dt[i+1][j-1], dt[i][j] + (j-1 != B)*a[i+1]);
}
if(j+m <= B+n && i+j+m-B <= n*m) {
dt[i][j+m] = min(dt[i][j+m], dt[i][j] + (j+m != B)*a[i+j+m-B]);
}
if(j+1 <= B+n && i+j+1-B <= n*m) {
dt[i][j+1] = min(dt[i][j+1], dt[i][j] + (j+1 != B)*a[i+j+1-B]);
}
}
}
printf("%d\n",dt[n*m][B]);
track(n*m, B);
if(f) swap(n, m);
for(int i=1;i<=m;i++) {
for(int j=1;j<=n;j++) {
printf("%d ",ans[n*(i-1)+j]);
}
puts("");
}
}
Compilation message
testdata.cpp: In function 'int main()':
testdata.cpp:38:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
^
testdata.cpp:41:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
215420 KB |
Wrong |
| 2 |
Halted |
0 ms |
0 KB |
- |
