結果
問題 | No.1916 Making Palindrome on Gird |
ユーザー |
![]() |
提出日時 | 2022-04-29 21:47:15 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 94 ms / 3,000 ms |
コード長 | 1,788 bytes |
コンパイル時間 | 2,286 ms |
コンパイル使用メモリ | 218,588 KB |
最終ジャッジ日時 | 2025-01-28 22:42:25 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>namespace {#pragma GCC diagnostic push#pragma GCC diagnostic ignored "-Wunused-function"#include<atcoder/all>#pragma GCC diagnostic popusing namespace std;using namespace atcoder;#define rep(i,n) for(int i = 0; i < (int)(n); i++)#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)#define all(x) begin(x), end(x)#define rall(x) rbegin(x), rend(x)template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }using ll = long long;using P = pair<int,int>;using VI = vector<int>;using VVI = vector<VI>;using VL = vector<ll>;using VVL = vector<VL>;using mint = modint1000000007;mint dp[210][210][210];const int di[] = {1, 0, -1, 0};const int dj[] = {0, 1, 0, -1};} int main() {ios::sync_with_stdio(false);cin.tie(0);int h, w;cin >> h >> w;vector<string> s(h);rep(i, h) cin >> s[i];if (s[0][0] != s[h - 1][w - 1]) {cout << 0 << '\n';return 0;}const int t = h + w - 2;dp[0][0][h-1] = 1;mint ans;rep(i, h) rep(j, w) {int s1 = i + j;int s2 = t - s1;if (s1 == s2) {ans += dp[i][j][i];break;} else if (s1 + 1 == s2) {ans += dp[i][j][i] + dp[i][j][i+1];break;} else if (s1 < s2) {rep(k, h) if (int l = s2 - k; 0 <= l && l < w) {rep(k1, 2) rep(k2, 2) {int ni = i + di[k1], nj = j + dj[k1];int nk = k - di[k2], nl = l - dj[k2];if (0 <= ni && ni < h && 0 <= nj && nj < w && 0 <= nk && nk < h && 0 <= nl && nl < w && s[ni][nj] == s[nk][nl]) {dp[ni][nj][nk] += dp[i][j][k];}}}}}cout << ans.val() << '\n';}