fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. #define MOD 1000000007
  6. #define MAX 505
  7. char matrix[MAX][MAX];
  8. int n, m;
  9.  
  10. void solve() {
  11.     cin >> n;
  12.     for (int i = 1; i <= n; i++) {
  13.         for (int j = 1; j <= n; j++) cin >> matrix[i][j];
  14.     }
  15.  
  16.     vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
  17.     vector<vector<int>> dp_next(n + 1, vector<int>(n + 1, 0));
  18.  
  19.     for (int i = 1; i <= n; i++) dp[i][i] = 1;
  20.  
  21.     for (int a = 0; a <= n - 1; a++) {
  22.         for (int r1 = 1; r1 <= n; r1++) {
  23.             for (int r2 = n; r2 >= 1; r2--) {
  24.                 int c1 = a + 2 - r1, c2 = 2 * n - a - r2;
  25.                 if (a + 1 > n - 1 || (matrix[r1][c1] != matrix[r2][c2])) continue;
  26.  
  27.                 if (r1 + 1 <= n) {
  28.                     // p xuong va q len
  29.                     if (r2 - 1 >= 1 && matrix[r1 + 1][c1] == matrix[r2 - 1][c2])
  30.                         dp_next[r1 + 1][r2 - 1] += dp[r1][r2] %= MOD;
  31.  
  32.                     // p xuong va q trai
  33.                     if (c2 - 1 >= 1 && matrix[r1 + 1][c1] == matrix[r2][c2 - 1])
  34.                         dp_next[r1 + 1][r2] += dp[r1][r2] %= MOD;
  35.                 }
  36.  
  37.                 // p phai q trai
  38.                 if (c1 + 1 <= n && c2 - 1 >= 1) {
  39.                     if (matrix[r1][c1 + 1] == matrix[r2][c2 - 1])
  40.                         dp_next[r1][r2] += dp[r1][r2] %= MOD;
  41.                 }
  42.  
  43.                 // p phai q len
  44.                 if (c1 + 1 <= n && r2 - 1 >= 1) {
  45.                     if (matrix[r1][c1 + 1] == matrix[r2 - 1][c2])
  46.                         dp_next[r1][r2 - 1] += dp[r1][r2] %= MOD;
  47.                 }
  48.             }
  49.         }
  50.  
  51.         for (int i = 0; i <= n; i++) {
  52.             for (int j = 0; j <= n; j++) {
  53.                 dp[i][j] = dp_next[i][j];
  54.                 dp_next[i][j] = 0;
  55.             }
  56.         }
  57.     }
  58.  
  59.     /*
  60.     for (int r1 = 1; r1 <= n; r1++) {
  61.         for (int r2 = n; r2 >= 1; r2--) {
  62.  
  63.             for (int i = 0; i <= n; i++) {
  64.                 for (int j = 0; j <= n; j++) {
  65.                     dp[i][j] = dp_next[i][j];
  66.                     dp_next[i][j] = 0;
  67.                 }
  68.             }
  69.  
  70.             for (int a = 0; a <= n - 1; a++) {
  71.                 int c1 = a + 2 - r1, c2 = 2 * n - a - r2;
  72.                 if (a + 1 > n - 1 || (matrix[r1][c1] != matrix[r2][c2])) continue;
  73.  
  74.                 if (r1 + 1 <= n) {
  75.                     // p xuong va q len
  76.                     if (r2 - 1 >= 1 && matrix[r1 + 1][c1] == matrix[r2 - 1][c2])
  77.                         dp_next[r1 + 1][r2 - 1] += dp[r1][r2] %= MOD;
  78.  
  79.                     // p xuong va q trai
  80.                     if (c2 - 1 >= 1 && matrix[r1 + 1][c1] == matrix[r2][c2 - 1])
  81.                         dp_next[r1 + 1][r2] += dp[r1][r2] %= MOD;
  82.                 }
  83.  
  84.                 // p phai q trai
  85.                 if (c1 + 1 <= n && c2 - 1 >= 1) {
  86.                     if (matrix[r1][c1 + 1] == matrix[r2][c2 - 1])
  87.                         dp_next[r1][r2] += dp[r1][r2] %= MOD;
  88.                 }
  89.  
  90.                 // p phai q len
  91.                 if (c1 + 1 <= n && r2 - 1 >= 1) {
  92.                     if (matrix[r1][c1 + 1] == matrix[r2 - 1][c2])
  93.                         dp_next[r1][r2 - 1] += dp[r1][r2] %= MOD;
  94.                 }
  95.             }
  96.         }
  97.     }
  98.  
  99.     int answer = 0;
  100.     for (int r1 = 1; r1 <= n; r1++) {
  101.         for (int r2 = 1; r2 <= n; r2++) {
  102.             for (int a = 0; a <= n - 1; a++) {
  103.                  int c1 = a + 2 - r1, c2 = 2 * n - a - r2;
  104.                  if (r1 + c1 == n + 1 && r2 + c2 == n + 1) answer += dp[r1][r2] %= MOD;
  105.             }
  106.         }
  107.     }
  108.     */
  109.  
  110.     int answer = 0;
  111.     for (int a = 0; a <= n - 1; a++) {
  112.         for (int r1 = 1; r1 <= n; r1++) {
  113.             for (int r2 = n; r2 >= 1; r2--) {
  114.                  int c1 = a + 2 - r1, c2 = 2 * n - a - r2;
  115.                  if (r1 + c1 == n + 1 && r2 + c2 == n + 1) answer += dp[r1][r2] %= MOD;
  116.             }
  117.         }
  118.     }
  119.  
  120.     cout << answer % MOD << '\n';
  121. }
  122.  
  123. signed main() {
  124.     ios_base::sync_with_stdio(false);
  125.     cin.tie(0);
  126.     // freopen("palpath.in", "r", stdin);
  127.     // freopen("palpath.out", "w", stdout);
  128.     solve();
  129. }
  130.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/T3BRh0
language:
C++14 (gcc 8.3)
created:
8 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!