結果

問題 No.1916 Making Palindrome on Gird
ユーザー SSRS
提出日時 2022-04-29 21:46:29
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 86 ms / 3,000 ms
コード長 2,251 bytes
コンパイル時間 3,154 ms
コンパイル使用メモリ 188,908 KB
実行使用メモリ 29,952 KB
最終ジャッジ日時 2024-06-29 03:08:35
合計ジャッジ時間 4,285 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main(){
  int H, W;
  cin >> H >> W;
  vector<vector<char>> S(H, vector<char>(W));
  for (int i = 0; i < H; i++){
    for (int j = 0; j < W; j++){
      cin >> S[i][j];
    }
  }
  if (S[0][0] != S[H - 1][W - 1]){
    cout << 0 << endl;
  } else {
    vector<vector<char>> c(H + W - 1);
    vector<vector<int>> id(H, vector<int>(W));
    for (int i = 0; i < H; i++){
      for (int j = 0; j < W; j++){
        id[i][j] = c[i + j].size();
        c[i + j].push_back(S[i][j]);
      }
    }
    vector<vector<vector<int>>> nxt(H + W - 1), prv(H + W - 1);
    for (int i = 0; i < H + W - 1; i++){
      nxt[i] = vector<vector<int>>(c[i].size());
      prv[i] = vector<vector<int>>(c[i].size());
    }
    for (int i = 0; i < H; i++){
      for (int j = 0; j < W; j++){
        if (i < H - 1){
          nxt[i + j][id[i][j]].push_back(id[i + 1][j]);
          prv[i + j + 1][id[i + 1][j]].push_back(id[i][j]);
        }
        if (j < W - 1){
          nxt[i + j][id[i][j]].push_back(id[i][j + 1]);
          prv[i + j + 1][id[i][j + 1]].push_back(id[i][j]);
        }
      }
    }
    int K = (H + W) / 2;
    vector<vector<vector<long long>>> dp(K);
    for (int i = 0; i < K; i++){
      dp[i] = vector<vector<long long>>(c[i].size(), vector<long long>(c[H + W - 2 - i].size(), 0));
    }
    dp[0][0][0] = 1;
    for (int i = 0; i < K - 1; i++){
      int s1 = c[i].size();
      int s2 = c[H + W - 2 - i].size();
      for (int j = 0; j < s1; j++){
        for (int k = 0; k < s2; k++){
          for (int j2 : nxt[i][j]){
            for (int k2 : prv[H + W - 2 - i][k]){
              if (c[i + 1][j2] == c[H + W - 3 - i][k2]){
                dp[i + 1][j2][k2] += dp[i][j][k];
                dp[i + 1][j2][k2] %= MOD;
              }
            }
          }
        }
      }
    }
    long long ans = 0;
    if ((H + W) % 2 == 0){
      int s = c[K - 1].size();
      for (int i = 0; i < s; i++){
        ans += dp[K - 1][i][i];
      }
    } else {
      int s = c[K - 1].size();
      for (int i = 0; i < s; i++){
        for (int j : nxt[K - 1][i]){
          ans += dp[K - 1][i][j];
        }
      }
    }
    ans %= MOD;
    cout << ans << endl;
  }
}
0