結果

問題 No.1916 Making Palindrome on Gird
ユーザー Mohamed Thaer
提出日時 2025-05-16 09:40:42
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,773 bytes
コンパイル時間 1,271 ms
コンパイル使用メモリ 83,928 KB
実行使用メモリ 817,664 KB
最終ジャッジ日時 2025-05-16 09:40:46
合計ジャッジ時間 4,189 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other AC * 6 WA * 4 MLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

const int MOD = 1000000007;

int main() {
    // Read input
    int H, W;
    cin >> H >> W;
    
    vector<vector<char>> grid(H+1, vector<char>(W+1));
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            cin >> grid[i][j];
        }
    }
    
    // Create 4D DP array
    // dp[i1][j1][i2][j2] = number of valid paths from (i1,j1) to (i2,j2)
    // We'll use a more memory-efficient approach with a custom index
    int M = max(H, W);
    vector<vector<vector<vector<int>>>> dp(H+1, vector<vector<vector<int>>>(W+1, 
                                           vector<vector<int>>(H+1, vector<int>(W+1, 0))));
    
    // Base cases: single point paths
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            dp[i][j][i][j] = 1;
        }
    }
    
    // Base cases: adjacent positions with matching characters
    for (int i = 1; i < H; i++) {
        for (int j = 1; j <= W; j++) {
            if (grid[i][j] == grid[i+1][j]) {
                dp[i][j][i+1][j] = 1;
            }
        }
    }
    
    for (int i = 1; i <= H; i++) {
        for (int j = 1; j < W; j++) {
            if (grid[i][j] == grid[i][j+1]) {
                dp[i][j][i][j+1] = 1;
            }
        }
    }
    
    // Fill the DP table using the optimized approach
    // Process in order of increasing distance between (i1,j1) and (i2,j2)
    for (int len = 3; len <= H + W - 1; len++) {
        for (int i1 = 1; i1 <= H; i1++) {
            for (int j1 = 1; j1 <= W; j1++) {
                for (int i2 = i1; i2 <= H; i2++) {
                    // Calculate j2 based on the constraint that (i1,j1) and (i2,j2) 
                    // are at distance len-2 (excluding the endpoints)
                    int j2 = len - (i2 - i1) - 1 + j1;
                    
                    if (j2 < j1 || j2 > W) continue;
                    
                    // Skip if characters don't match
                    if (grid[i1][j1] != grid[i2][j2]) continue;
                    
                    // Apply the transition formula
                    if (i1 < i2 && j1 < j2) {
                        dp[i1][j1][i2][j2] = (
                            (i1+1 <= i2-1 ? dp[i1+1][j1][i2-1][j2] : 0) + 
                            (j2-1 >= j1 ? dp[i1+1][j1][i2][j2-1] : 0) + 
                            (i2-1 >= i1 ? dp[i1][j1+1][i2-1][j2] : 0) + 
                            (j2-1 >= j1+1 ? dp[i1][j1+1][i2][j2-1] : 0)
                        ) % MOD;
                    }
                }
            }
        }
    }
    
    // The answer is the number of valid paths from (1,1) to (H,W)
    cout << dp[1][1][H][W] << endl;
    
    return 0;
}
0