結果

問題 No.1916 Making Palindrome on Gird
ユーザー Mohamed Thaer
提出日時 2025-05-16 10:00:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 216 ms / 3,000 ms
コード長 1,539 bytes
コンパイル時間 2,355 ms
コンパイル使用メモリ 214,464 KB
実行使用メモリ 70,784 KB
最終ジャッジ日時 2025-05-16 10:00:41
合計ジャッジ時間 5,797 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘void Thaer()’:
main.cpp:48:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   48 |         freopen("input.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:49:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   49 |         freopen("output.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
//#define int int64_t
#define el '\n'
const int MOD=1e9+7;
void Main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> grid(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    vector<vector<vector<int64_t>>> dp(n, vector<vector<int64_t>>(m, vector<int64_t>(n, 0)));
    vector<vector<vector<bool>>> vis(n, vector<vector<bool>>(m, vector<bool>(n, 0)));
    function<int64_t(int, int, int, int)> solve = [&](int i, int j, int ii, int jj) -> int64_t {
        if (i >= n || j >= m || ii < i || jj < j)return 0;
        if (grid[i][j] != grid[ii][jj])return 0;
        if (abs(i - ii) + abs(j - jj) <= 1)return 1;
        if (vis[i][j][ii])return dp[i][j][ii];
        vis[i][j][ii] = 1;
        int64_t &ret = dp[i][j][ii];
        ret += solve(i + 1, j, ii - 1, jj);
        ret %= MOD;
        ret += solve(i, j + 1, ii, jj - 1);
        ret %= MOD;
        ret += solve(i + 1, j, ii, jj - 1);
        ret %= MOD;
        ret += solve(i, j + 1, ii - 1, jj);
        return ret %= MOD;
    };
    cout << solve(0, 0, n - 1, m - 1) << el;
}
void Thaer();
int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    // Thaer();
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; ++i) {
        Main();
        // if (i != T)cout << el;
    }
}
void Thaer() {
    if (fopen("input.txt", "r")) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
}
0