Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <list>
- #include <map>
- #include <set>
- #include <deque>
- #include <stack>
- #include <queue>
- #include <algorithm>
- #include <sstream>
- #include <iostream>
- #include <iomanip>
- #include <cstdio>
- #include <cmath>
- #include <cstdlib>
- #include <memory.h>
- #include <ctime>
- #include <bitset>
- using namespace std;
- #define ABS(a) ((a>0)?a:-(a))
- #define MIN(a,b) ((a<b)?(a):(b))
- #define MAX(a,b) ((a<b)?(b):(a))
- #define FOR(i,a,n) for (int i=(a);i<(n);++i)
- #define FI(i,n) for (int i=0; i<(n); ++i)
- #define pnt pair <int, int>
- #define mp make_pair
- #define PI 3.1415926535897
- #define MEMS(a,b) memset(a,b,sizeof(a))
- #define LL long long
- #define U unsigned
- #define V vector
- int a[2050][2050];
- int b[2050][2050];
- int c[2050][2050];
- int n, m;
- bool check()
- {
- FOR(i, 1, n)
- {
- FOR(j, 1, m)
- {
- if (a[i][j] >= a[i][j + 1])
- return false;
- if (a[i][j] >= a[i + 1][j])
- return false;
- }
- }
- return true;
- }
- void solution()
- {
- cin >> n >> m;
- MEMS(a, 0);
- char odd = 0;
- char even = 0;
- FOR(i, 1, n + 1)
- {
- FOR(j, 1, m + 1)
- {
- scanf("%d", &a[i][j]);
- }
- }
- if (n == 1)
- {
- int mx = 0;
- FOR(j, 1, m + 1)
- {
- if (a[n][j])
- mx = a[n][j];
- else
- {
- mx++;
- a[n][j] = mx;
- }
- }
- mx = 0;
- FOR(j, 1, m)
- {
- if (a[n][j + 1] <= a[n][j])
- {
- cout << "-1" << endl;
- return;
- }
- mx += a[n][j];
- }
- cout << mx + a[n][m] << endl;
- return;
- }
- if (m == 1)
- {
- int mx = 0;
- FOR(i, 1, n + 1)
- {
- if (a[i][m])
- mx = a[i][m];
- else
- {
- mx++;
- a[i][m] = mx;
- }
- }
- mx = 0;
- FOR(i, 1, n)
- {
- if (a[i + 1][m] <= a[i][m])
- {
- cout << "-1" << endl;
- return;
- }
- mx += a[i][m];
- }
- cout << mx + a[n][m] << endl;
- return;
- }
- LL ans = -1;
- // CASE 1
- FOR(PPP, 0, 2)
- {
- FOR(i, 1, n + 1)
- {
- FOR(j, 1, m + 1)
- {
- b[j][i] = a[i][j];
- }
- }
- memcpy(c, a, sizeof(a));
- LL sum = 0;
- char good = 1;
- int q = a[1][1];
- if (q == 0)
- a[1][1] = 1;
- FOR(i, 1, n + 1)
- {
- FOR(j, 1, m + 1)
- {
- if ((j & 1) == 0)
- {
- if (a[i][j])
- {
- if (a[i][j] & 1)
- good = 0;
- }
- else
- {
- a[i][j] = 1 + MAX(a[i - 1][j], a[i][j - 1]);
- if (a[i][j] & 1)
- a[i][j]++;
- }
- }
- else
- {
- if (a[i][j])
- {
- if ((a[i][j] & 1) == 0)
- good = 0;
- }
- else
- {
- a[i][j] = 1 + MAX(a[i - 1][j], a[i][j - 1]);
- if ((a[i][j] & 1) == 0)
- a[i][j]++;
- }
- }
- sum += a[i][j];
- }
- }
- if (good && check())
- {
- if (ans == -1)
- ans = sum;
- else
- ans = MIN(ans, sum);
- }
- a[1][1] = q;
- good = 1;
- sum = 0;
- memcpy(a, c, sizeof(a));
- q = a[1][1];
- if (a[1][1] == 0)
- a[1][1] = 2;
- FOR(i, 1, n + 1)
- {
- FOR(j, 1, m + 1)
- {
- if (j & 1)
- {
- if (a[i][j])
- {
- if (a[i][j] & 1)
- good = 0;
- }
- else
- {
- a[i][j] = 1 + MAX(a[i - 1][j], a[i][j - 1]);
- if (a[i][j] & 1)
- a[i][j]++;
- }
- }
- else
- {
- if (a[i][j])
- {
- if ((a[i][j] & 1) == 0)
- good = 0;
- }
- else
- {
- a[i][j] = 1 + MAX(a[i - 1][j], a[i][j - 1]);
- if ((a[i][j] & 1) == 0)
- a[i][j]++;
- }
- }
- sum += a[i][j];
- }
- }
- if (good && check())
- {
- if (ans == -1)
- ans = sum;
- else
- ans = MIN(ans, sum);
- }
- a[1][1] = q;
- swap(n, m);
- memcpy(a, b, sizeof(a));
- }
- //
- cout << ans << endl;
- return;
- }
- int main()
- {
- #ifdef Fcdkbear
- freopen("in.txt", "r", stdin);
- //freopen("out.txt", "w", stdout);
- double beg = clock();
- #endif
- solution();
- #ifdef Fcdkbear
- double end = clock();
- fprintf(stderr, "*** Total time = %.3lf ***\n", (end - beg) / CLOCKS_PER_SEC);
- #endif
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement