結果

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

ソースコード

diff # 

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