結果
問題 |
No.1916 Making Palindrome on Gird
|
ユーザー |
|
提出日時 | 2025-05-16 11:59:09 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,834 bytes |
コンパイル時間 | 1,990 ms |
コンパイル使用メモリ | 211,300 KB |
実行使用メモリ | 7,848 KB |
最終ジャッジ日時 | 2025-05-16 11:59:19 |
合計ジャッジ時間 | 9,907 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 WA * 5 |
ソースコード
#include <bits/stdc++.h> using namespace std; constexpr int MOD = 1e9 + 7; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int H, W; cin >> H >> W; vector<vector<char>> grid(H, vector<char>(W)); for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) cin >> grid[i][j]; if (grid[0][0] != grid[H - 1][W - 1]) { cout << "0\n"; return 0; } // State compression: (i,j,k,l) -> single integer key auto index = [=](int i, int j, int k, int l) { return ((i * W + j) * H + k) * W + l; }; unordered_map<ll, int> dp; dp[index(0, 0, H - 1, W - 1)] = 1; int total_steps = H + W - 2; // Expand DP: for each step towards the middle for (int dist = 0; dist < (total_steps + 1) / 2; ++dist) { unordered_map<ll, int> next_dp; for (auto &pr : dp) { ll key = pr.first, val = pr.second; int tmp = key; int l = tmp % W; tmp /= W; int k = tmp % H; tmp /= H; int j = tmp % W; tmp /= W; int i = tmp; // Try all (right,down) from (i,j) for (auto [ni, nj] : vector<pair<int,int>>{{i+1,j}, {i,j+1}}) { if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue; // Try all (left,up) from (k,l) for (auto [nk, nl] : vector<pair<int,int>>{{k-1,l}, {k,l-1}}) { if (nk < 0 || nk >= H || nl < 0 || nl >= W) continue; if (grid[ni][nj] == grid[nk][nl]) { next_dp[index(ni, nj, nk, nl)] = (next_dp[index(ni, nj, nk, nl)] + val) % MOD; } } } } dp = move(next_dp); } ll ans = 0; // Even length path: middle is a pair if (total_steps % 2 == 1) { int mid = total_steps / 2; for (auto &pr : dp) { int tmp = pr.first; int l = tmp % W; tmp /= W; int k = tmp % H; tmp /= H; int j = tmp % W; tmp /= W; int i = tmp; // Only left-right pair at midpoint if ((i + j == mid) && (k + l == H + W - 2 - mid) && ((abs(i - k) + abs(j - l)) == 1)) { ans = (ans + pr.second) % MOD; } } } // Odd length path: middle is a cell else { int mid = total_steps / 2; for (auto &pr : dp) { int tmp = pr.first; int l = tmp % W; tmp /= W; int k = tmp % H; tmp /= H; int j = tmp % W; tmp /= W; int i = tmp; if ((i == k) && (j == l) && (i + j == mid)) { ans = (ans + pr.second) % MOD; } } } cout << ans << '\n'; }