結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー |
👑 ![]() |
提出日時 | 2022-04-29 23:38:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 104 ms / 3,000 ms |
コード長 | 2,772 bytes |
コンパイル時間 | 1,695 ms |
コンパイル使用メモリ | 179,008 KB |
実行使用メモリ | 67,840 KB |
最終ジャッジ日時 | 2024-06-29 05:25:24 |
合計ジャッジ時間 | 4,452 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define repr(i, n) for (int i = (int)(n); i >= 0; i--)#define all(v) v.begin(), v.end()#define mod1 1000000007#define mod2 998244353typedef long long ll;int main(){ll H,W;cin >> H >> W;vector<string> S(H);rep(i,H){cin >> S[i];}ll len = H + W - 2;vector<vector<vector<ll>>> dp(len / 2 + 1, vector<vector<ll>>(H, vector<ll>(H, 0)));if (S[0][0] == S[H - 1][W - 1]){dp[0][0][0] = 1;}else{dp[0][0][0] = 0;}for (ll i = 0; i < len / 2; i++){//i + 1: 進んだ文字の数.j: 縦.(i + 1 - j):横.H - 1 - k: 縦.for (ll j = 0; j <= i; j++){for (ll k = 0; k <= i; k++){if (j < H && i + 1 - j < W && H - 1 - k >= 0 && W - 2 - i + k >= 0){//横,横if (S[j][i + 1 - j] == S[H - 1 - k][W - 1 - (i + 1 - k)]){dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % mod1;}}if (j < H && i + 1 - j < W && H - 1 - k - 1 >= 0 && W - 1 - (i + 1 - k - 1) >= 0){//横,縦if (S[j][i + 1 - j] == S[H - 1 - k - 1][W - 1 - i + k]){dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % mod1;}}if (j + 1 < H && i - j < W && H - 1 - k >= 0 && W - 1 - (i + 1 - k) >= 0){//縦,横if (S[j + 1][i - j] == S[H - 1 - k][W - 1 - (i + 1 - k)]){dp[i + 1][j + 1][k] = (dp[i + 1][j + 1][k] + dp[i][j][k]) % mod1;}}if (j + 1 < H && i - j < W && H - 1 - k - 1 >= 0 && W - 1 - (i + 1 - k - 1) >= 0){//縦,縦if (S[j + 1][i - j] == S[H - 1 - k - 1][W - 1 - (i + 1 - k - 1)]){dp[i + 1][j + 1][k + 1] = (dp[i + 1][j + 1][k + 1] + dp[i][j][k]) % mod1;}}}}}/*for (ll i = 0; i <= len / 2; i++){for (ll j = 0; j < H; j++){for (ll k = 0; k < H; k++){cout << dp[i][j][k] << " ";}cout << endl;}}*/ll ans = 0;if (len % 2 == 0){for (ll j = 0; j < H; j++){for (ll k = 0; k < H; k++){if (j + k == H - 1) ans = (ans + dp[len / 2][j][k]) % mod1;}}}else{for (ll j = 0; j < H; j++){for (ll k = 0; k < H; k++){if (j + k == H - 1 || j + k == H - 2) ans = (ans + dp[len / 2][j][k]) % mod1;}}}cout << ans << endl;}