結果

問題 No.1916 Making Palindrome on Gird
コンテスト
ユーザー Mohamed Thaer
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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';
}
0