fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. const int MAXN = 515;
  6. const int MOD  = 1e9 + 7;
  7.  
  8. int N;
  9. char A[MAXN][MAXN];
  10. int dp[MAXN][MAXN], pre[MAXN][MAXN];
  11.  
  12.  
  13. signed main() {
  14.     ios_base::sync_with_stdio(0);
  15.     cin.tie(0);
  16.     cout.tie(0);
  17.  
  18. //    freopen("RPATH.inp", "r", stdin);
  19. //    freopen("RPATH.out", "w", stdout);
  20.  
  21.     cin >> N;
  22.     for (int i = 1; i <= N; i++) {
  23.         for (int j = 1; j <= N; j++) {
  24.             cin >> A[i][j];
  25.         }
  26.     }
  27.     if (A[1][1] != A[N][N]) {
  28.         cout << 0;
  29.         return 0;
  30.     }
  31.  
  32.     pre[1][N] = dp[1][N] = 1;
  33.  
  34.  
  35.     for (int t = 2; t <= N; t++) {
  36.         for (int ai = 1; ai <= N; ai++) {
  37.             for (int bi = 1; bi <= N; bi++) {
  38.                 int ay = t - ai + 1, by = N - (t - (N - bi + 1) + 1) + 1;
  39.                 dp[ai][bi] = 0;
  40.                 if (t - ai < 0 || t - (N - bi + 1) < 0) continue;
  41.                 if (ay < 1 || ay > N || by < 1 || by > N) continue;
  42.  
  43.  
  44.                 if (A[ai][ay] == A[bi][by]) {
  45.                     if (ai > 1 && bi < N)  dp[ai][bi] = (dp[ai][bi] +  pre[ai - 1][bi + 1]) % MOD;
  46.                     if (bi < N) dp[ai][bi] = (dp[ai][bi]  + pre[ai][bi + 1]) % MOD;
  47.                     if (ai > 1) dp[ai][bi] = (dp[ai][bi]  + pre[ai - 1][bi]) % MOD;
  48.                     dp[ai][bi] = (dp[ai][bi]  + pre[ai][bi]) % MOD;
  49.                 }
  50.             }
  51.         }
  52.         for (int i = 1; i <= N; i++) {
  53.             for (int j = 1; j <= N; j++) {
  54.                 pre[i][j] = dp[i][j];
  55.             }
  56.         }
  57.     }
  58.  
  59.     int ans = 0;
  60.     for (int ai = 1; ai <= N; ai++) {
  61.         for (int bi = 1; bi <= N; bi++) {
  62.             int ay = N - ai + 1, by = N - (N - (N - bi + 1) + 1) + 1;
  63.             //cout << ai << ' ' << ay << ' ' << bi << ' ' << by << ' ';
  64.             if (ai == bi && ay == by) {
  65. //                cout << 1 << ' ';
  66. //                cout << dp[ai][bi] << ' ';
  67.                 ans += dp[ai][bi];
  68.             }
  69.             //cout << '\n';
  70.         }
  71.     }
  72.  
  73.     cout << ans;
  74. }
  75.  
Success #stdin #stdout 0.01s 5652KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/sj6zju
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!