結果
問題 |
No.1916 Making Palindrome on Gird
|
ユーザー |
|
提出日時 | 2025-05-16 12:08:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,416 bytes |
コンパイル時間 | 2,530 ms |
コンパイル使用メモリ | 195,708 KB |
実行使用メモリ | 35,412 KB |
最終ジャッジ日時 | 2025-05-16 12:08:30 |
合計ジャッジ時間 | 5,559 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 WA * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; int N, M; vector<string> grid; int dp[201][201][201]; // Returns number of palindromic paths from (i1,j1) coming from (0,0) // and (i2,j2) coming from (N-1, M-1) // where t = number of steps from start, and (i2, j2) can be calculated from t int solve(int i1, int j1, int i2) { int t = i1 + j1; int j2 = N + M - 2 - t - i2; // Out of bounds if (i1 >= N || j1 >= M || i2 < 0 || j2 < 0 || i2 >= N || j2 >= M) return 0; // Current grid cells do not match if (grid[i1][j1] != grid[i2][j2]) return 0; // If the pointers have crossed or met (at center or adjacent) if (abs(i1 - i2) + abs(j1 - j2) <= 1) return 1; int &res = dp[i1][j1][i2]; if (res != -1) return res; res = 0; // 4 ways to move: (down/down), (right/right), (down/right), (right/down) res = (res + solve(i1 + 1, j1, i2 - 1)) % MOD; // down, up res = (res + solve(i1, j1 + 1, i2 - 1)) % MOD; // right, up res = (res + solve(i1 + 1, j1, i2)) % MOD; // down, left res = (res + solve(i1, j1 + 1, i2)) % MOD; // right, left return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N >> M; grid.resize(N); for (int i = 0; i < N; ++i) cin >> grid[i]; memset(dp, -1, sizeof dp); cout << solve(0, 0, N - 1) << '\n'; return 0; }