Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define all(a) (a).begin(), (a).end()
- const int mod = 1000000007;
- const int maxn = 1005;
- int a[maxn][maxn];
- int x[maxn];
- int y[maxn];
- int dp[maxn][maxn];
- int used[maxn][maxn];
- int n, m;
- int dx[] = {1, -1, 0, 0};
- int dy[] = {0, 0, 1, -1};
- int k = 0;
- void dfs(int i, int j) {
- if (used[i][j])
- return;
- used[i][j] = 1;
- for (int h = 0; h < 4; ++h) {
- if (i + dx[h] < n && i + dx[h] >= 0 && j + dy[h] < m && j + dy[h] >= 0) {
- if (a[i][j] + 1 != a[i + dx[h]][j + dy[h]])
- continue;
- dfs(i + dx[h], j + dy[h]);
- }
- }
- x[k] = i;
- y[k] = j;
- k++;
- }
- void solve() {
- cin >> n >> m;
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- cin >> a[i][j];
- }
- }
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) {
- if (a[i][j] == 1) {
- dfs(i, j);
- }
- }
- }
- reverse(x, x + k);
- reverse(y, y + k);
- int ans = 0;
- for (int v = 0; v < k; ++v) {
- int i = x[v];
- int j = y[v];
- dp[i][j] = max(dp[i][j], 1);
- bool end = true;
- for (int h = 0; h < 4; ++h) {
- if (i + dx[h] < n && i + dx[h] >= 0 && j + dy[h] < m && j + dy[h] >= 0) {
- if (a[i][j] + 1 != a[i + dx[h]][j + dy[h]])
- continue;
- dp[i + dx[h]][j + dy[h]] += dp[i][j];
- dp[i + dx[h]][j + dy[h]] %= mod;
- end = false;
- }
- }
- if (end) {
- ans += dp[i][j];
- ans %= mod;
- }
- }
- cout << ans << '\n';
- }
- signed main() {
- ios::sync_with_stdio(0); cin.tie(0);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement