Advertisement
Gosunov

Untitled

Oct 24th, 2022
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(a) (a).begin(), (a).end()
  4.  
  5. const int mod = 1000000007;
  6. const int maxn = 1010;
  7. int a[maxn][maxn];
  8. int x[maxn*maxn];
  9. int y[maxn*maxn];
  10. int dp[maxn][maxn][4];
  11. int used[maxn][maxn];
  12. int used2[maxn][maxn];
  13.  
  14. int n, m;
  15.  
  16. int dx[] = {1, -1, 0, 0};
  17. int dy[] = {0, 0, 1, -1};
  18.  
  19. int k = 0;
  20. void dfs(int i, int j) {
  21.     if (used[i][j])
  22.         return;
  23.     used[i][j] = 1;
  24.     for (int h = 0; h < 4; ++h) {
  25.         if (i + dx[h] < n && i + dx[h] >= 0 && j + dy[h] < m && j + dy[h] >= 0) {
  26.             if (a[i][j] + 1 != a[i + dx[h]][j + dy[h]])
  27.                 continue;
  28.             dfs(i + dx[h], j + dy[h]);
  29.         }
  30.     }
  31.     x[k] = i;
  32.     y[k] = j;
  33.     k++;
  34. }
  35.  
  36. void solve() {
  37.     cin >> n >> m;
  38.     for (int i = 0; i < n; ++i) {
  39.         for (int j = 0; j < m; ++j) {
  40.             cin >> a[i][j];
  41.         }
  42.     }
  43.     for (int i = 0; i < n; ++i) {
  44.         for (int j = 0; j < m; ++j) {
  45.             dfs(i, j);
  46.         }
  47.     }
  48.     reverse(x, x + k);
  49.     reverse(y, y + k);
  50.  
  51.     int ans = 0;
  52.     for (int v = 0; v < k; ++v) {
  53.         int i = x[v];
  54.         int j = y[v];
  55.        
  56.         if (!used2[i][j]) {
  57.             dp[i][j][0] = 1;
  58.             used2[i][j] = 1;
  59.         }
  60.        
  61.         bool end = true;
  62.         for (int h = 0; h < 4; ++h) {
  63.             if (i + dx[h] < n && i + dx[h] >= 0 && j + dy[h] < m && j + dy[h] >= 0) {
  64.                 if (a[i][j] + 1 != a[i + dx[h]][j + dy[h]])
  65.                     continue;
  66.                 dp[i + dx[h]][j + dy[h]][1] += dp[i][j][0];
  67.                 dp[i + dx[h]][j + dy[h]][1] %= mod;
  68.                 dp[i + dx[h]][j + dy[h]][2] += dp[i][j][1];
  69.                 dp[i + dx[h]][j + dy[h]][2] %= mod;
  70.                 dp[i + dx[h]][j + dy[h]][3] += dp[i][j][2];
  71.                 dp[i + dx[h]][j + dy[h]][3] %= mod;
  72.                 dp[i + dx[h]][j + dy[h]][3] += dp[i][j][3];
  73.                 dp[i + dx[h]][j + dy[h]][3] %= mod;
  74.                 used2[i + dx[h]][j + dy[h]] = 1;
  75.                
  76.                 end = false;
  77.             }
  78.         }
  79.         if (end) {
  80.             ans += dp[i][j][3];
  81.             ans %= mod;
  82.         }
  83.     }
  84.     cout << ans << '\n';
  85. }
  86.  
  87. signed main() {
  88.     ios::sync_with_stdio(0); cin.tie(0);
  89.     solve();
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement