Advertisement
Gosunov

Untitled

Oct 24th, 2022
110
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 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 = 1005;
  7. int a[maxn][maxn];
  8. int x[maxn];
  9. int y[maxn];
  10. int dp[maxn][maxn];
  11. int used[maxn][maxn];
  12.  
  13. int n, m;
  14.  
  15. int dx[] = {1, -1, 0, 0};
  16. int dy[] = {0, 0, 1, -1};
  17.  
  18. int k = 0;
  19. void dfs(int i, int j) {
  20.     if (used[i][j])
  21.         return;
  22.     used[i][j] = 1;
  23.     for (int h = 0; h < 4; ++h) {
  24.         if (i + dx[h] < n && i + dx[h] >= 0 && j + dy[h] < m && j + dy[h] >= 0) {
  25.             if (a[i][j] + 1 != a[i + dx[h]][j + dy[h]])
  26.                 continue;
  27.             dfs(i + dx[h], j + dy[h]);
  28.         }
  29.     }
  30.     x[k] = i;
  31.     y[k] = j;
  32.     k++;
  33. }
  34.  
  35. void solve() {
  36.     cin >> n >> m;
  37.     for (int i = 0; i < n; ++i) {
  38.         for (int j = 0; j < m; ++j) {
  39.             cin >> a[i][j];
  40.         }
  41.     }
  42.     for (int i = 0; i < n; ++i) {
  43.         for (int j = 0; j < m; ++j) {
  44.             if (a[i][j] == 1) {
  45.                 dfs(i, j);
  46.             }
  47.         }
  48.     }
  49.     reverse(x, x + k);
  50.     reverse(y, y + k);
  51.  
  52.     int ans = 0;
  53.     for (int v = 0; v < k; ++v) {
  54.         int i = x[v];
  55.         int j = y[v];
  56.         dp[i][j] = max(dp[i][j], 1);
  57.         bool end = true;
  58.         for (int h = 0; h < 4; ++h) {
  59.             if (i + dx[h] < n && i + dx[h] >= 0 && j + dy[h] < m && j + dy[h] >= 0) {
  60.                 if (a[i][j] + 1 != a[i + dx[h]][j + dy[h]])
  61.                     continue;
  62.                 dp[i + dx[h]][j + dy[h]] += dp[i][j];
  63.                 dp[i + dx[h]][j + dy[h]] %= mod;
  64.                 end = false;
  65.             }
  66.         }
  67.         if (end) {
  68.             ans += dp[i][j];
  69.             ans %= mod;
  70.         }
  71.     }
  72.     cout << ans << '\n';
  73. }
  74.  
  75. signed main() {
  76.     ios::sync_with_stdio(0); cin.tie(0);
  77.     solve();
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement