結果
問題 |
No.1916 Making Palindrome on Gird
|
ユーザー |
|
提出日時 | 2025-05-16 10:11:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,199 bytes |
コンパイル時間 | 878 ms |
コンパイル使用メモリ | 77,924 KB |
実行使用メモリ | 35,328 KB |
最終ジャッジ日時 | 2025-05-16 10:11:57 |
合計ジャッジ時間 | 4,502 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 2 |
other | AC * 9 WA * 21 |
ソースコード
#include <iostream> #include <vector> using namespace std; const int MOD = 1000000007; int H, W; vector<string> grid; int dp[201][201][201]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> H >> W; grid.resize(H + 1); for (int i = 1; i <= H; ++i) { string s; cin >> s; grid[i] = " " + s; // 1-index } // DP base: checking if the first and last cell match for (int i1 = 1; i1 <= H; ++i1) { for (int j1 = 1; j1 <= W; ++j1) { int i2 = H + 1 - i1; int j2 = W + 1 - j1; if (i2 >= 1 && i2 <= H && j2 >= 1 && j2 <= W && grid[i1][j1] == grid[i2][j2]) dp[0][i1][j1] = 1; } } int L = (H + W - 2) / 2; for (int s = 0; s < L; ++s) { for (int i1 = 1; i1 <= H; ++i1) for (int j1 = 1; j1 <= W; ++j1) { int cur = dp[s][i1][j1]; if (cur == 0) continue; int i2 = H + 1 - i1; int j2 = W + 1 - j1; // Four directions: (down-down), (down-right), (right-down), (right-right) for (int d1 = 0; d1 < 2; ++d1) for (int d2 = 0; d2 < 2; ++d2) { int ni1 = i1 + d1, nj1 = j1 + (1 - d1); int ni2 = i2 - d2, nj2 = j2 - (1 - d2); if (ni1 > H || nj1 > W || ni2 < 1 || nj2 < 1) continue; if (grid[ni1][nj1] == grid[ni2][nj2]) { dp[s + 1][ni1][nj1] = (dp[s + 1][ni1][nj1] + cur) % MOD; } } } } int result = 0; // Odd length: pointers meet at a cell if ((H + W) % 2 == 1) { for (int i1 = 1; i1 <= H; ++i1) for (int j1 = 1; j1 <= W; ++j1) { int i2 = H + 1 - i1; int j2 = W + 1 - j1; if (i2 == i1 && j2 == j1) result = (result + dp[L][i1][j1]) % MOD; } } else { // Even length: pointers meet at an edge for (int i1 = 1; i1 <= H; ++i1) for (int j1 = 1; j1 <= W; ++j1) { int i2 = H + 1 - i1; int j2 = W + 1 - j1; if ((abs(i1 - i2) + abs(j1 - j2)) == 1) result = (result + dp[L][i1][j1]) % MOD; } } cout << result << '\n'; }