結果

問題 No.1916 Making Palindrome on Gird
ユーザー SSRSSSRS
提出日時 2022-04-29 21:46:29
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 89 ms / 3,000 ms
コード長 2,251 bytes
コンパイル時間 1,999 ms
コンパイル使用メモリ 186,872 KB
実行使用メモリ 29,904 KB
最終ジャッジ日時 2023-09-11 12:44:52
合計ジャッジ時間 4,358 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 1 ms
4,380 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 35 ms
14,256 KB
testcase_14 AC 22 ms
10,156 KB
testcase_15 AC 41 ms
16,368 KB
testcase_16 AC 29 ms
12,972 KB
testcase_17 AC 74 ms
26,916 KB
testcase_18 AC 82 ms
29,808 KB
testcase_19 AC 82 ms
29,904 KB
testcase_20 AC 82 ms
29,792 KB
testcase_21 AC 83 ms
29,808 KB
testcase_22 AC 84 ms
29,808 KB
testcase_23 AC 3 ms
4,376 KB
testcase_24 AC 3 ms
4,376 KB
testcase_25 AC 3 ms
4,380 KB
testcase_26 AC 4 ms
4,376 KB
testcase_27 AC 4 ms
4,376 KB
testcase_28 AC 87 ms
29,828 KB
testcase_29 AC 88 ms
29,800 KB
testcase_30 AC 87 ms
29,828 KB
testcase_31 AC 87 ms
29,900 KB
testcase_32 AC 89 ms
29,892 KB
権限があれば一括ダウンロードができます

ソースコード

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