結果
問題 |
No.2708 Jewel holder
|
ユーザー |
|
提出日時 | 2024-03-31 14:12:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,915 bytes |
コンパイル時間 | 2,233 ms |
コンパイル使用メモリ | 192,040 KB |
最終ジャッジ日時 | 2025-02-20 17:03:49 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
ソースコード
#include <bits/stdc++.h> // clang-format off using namespace std; using ll=long long; using ull=unsigned long long; using pll=pair<ll,ll>; const ll INF=4e18; void print0(){}; template<typename H,typename... T> void print0(H h,T... t){cout<<h;print0(t...);} void print1(){print0("\n");}; template<typename H,typename... T>void print1(H h,T... t){print0(h);if(sizeof...(T)>0)print0(" ");print1(t...);} void ioinit() { cout<<fixed<<setprecision(15); cerr<<fixed<<setprecision(6); ios_base::sync_with_stdio(0); cin.tie(0); } #define debug1(a) { cerr<<#a<<":"<<a<<endl; } #define debug2(a,b) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<endl; } #define debug3(a,b,c) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<endl; } #define debug4(a,b,c,d) { cerr<<#a<<":"<<a<<" "<<#b<<":"<<b<<" "<<#c<<":"<<c<<" "<<#d<<":"<<d<<endl; } // clang-format on char tbl[10][10]; ll H, W; ll dp(ll i, ll j, ll jewel) { // static ll dp[11][11][2]; // static bool done[11][11][2]; if (jewel < 0) return 0; if (i == H - 1 && j == W - 1) { return 1; } ll ans = 0; if (i + 1 < H && tbl[i + 1][j] != '#') { ll wadd = 0; if (tbl[i + 1][j] == 'x') { wadd = -1; } if (tbl[i + 1][j] == 'o') { wadd = 1; } ans += dp(i + 1, j, jewel + wadd); } if (j + 1 < W && tbl[i][j + 1] != '#') { ll wadd = 0; if (tbl[i][j + 1] == 'x') { wadd = -1; } if (tbl[i][j + 1] == 'o') { wadd = 1; } ans += dp(i, j + 1, jewel + wadd); } return ans; } int main() { ioinit(); cin >> H >> W; for (ll r = 0; r < H; r++) { for (ll c = 0; c < W; c++) { cin >> tbl[r][c]; } } ll ini = 0; if (tbl[0][0] == 'o') { ini = 1; } if (tbl[0][0] == 'x') { ini = -1; } print1(dp(0, 0, ini)); return 0; }