fork download
copy 
  1. // ROOT : DRAGON3012009 : WA in Real Life
  2. #include <bits/stdc++.h>
  3. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  4. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  5. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  6. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  7. #define ll int
  8. #define el "\n"
  9. #define fi first
  10. #define se second
  11. #define _ROOT_ int main()
  12. #define M 998244353
  13. #define MAXN 31
  14. #define INF (1ll<<30)
  15. #define NAME "file"
  16. using namespace std;
  17.  
  18. ll dx[] = {0, 1, 0, - 1 } ;
  19. ll dy[] = {1, 0, -1, 0  } ;
  20.  
  21. ll n, m, k ;
  22. ll dp[MAXN][MAXN][MAXN][MAXN][11][4]; // | left , - top , l right , -bot , cur_k , dir , ok ;
  23. char a[MAXN][MAXN ] ;
  24.  
  25. ll Power(ll a, ll b ) { ll res = 1; while(b){ if(b&1) res = a*res%M; b>>=1; a=a*a%M; } return res; }
  26. ll add(ll a, ll b ) { return a + b >= M ? a + b - M : a + b; }
  27. ll mul(ll a, ll b )  { return 1LL * (a%M) * (b%M) % M; }
  28. ll sub(ll a, ll b ) { return a - b < 0 ? a - b + M : a - b; }
  29. ll divi(ll a, ll b) { return 1LL * a * Power(b, M - 2 ) % M; }
  30.  
  31. bool in(ll cur_x, ll cur_y, ll left, ll top, ll right, ll bot ) {
  32.     return left < cur_y && cur_y < right && top < cur_x && cur_x < bot;
  33. }
  34.  
  35. ll DP(ll lim_left, ll lim_top, ll lim_right, ll lim_bot, ll cur_k, ll cur_dir  ) {
  36.     ll &cur = dp[lim_left][lim_top][lim_right][lim_bot][cur_k][cur_dir] ;
  37.     if(cur != - 1 ) return cur ;
  38.     cur = 0 ;
  39.     ll x, y ;
  40.     if(cur_dir == 0 ) x = lim_top + 1 , y = lim_left + 1 ;
  41.     else if(cur_dir == 1 ) x = lim_top + 1, y = lim_right - 1  ;
  42.     else if(cur_dir == 2 ) x = lim_bot - 1 , y = lim_right - 1  ;
  43.     else x = lim_bot - 1 , y = lim_left + 1  ;
  44.         ll nxt_k = cur_k;
  45.  
  46.     while(in(x, y, lim_left, lim_top, lim_right, lim_bot )) {
  47.  
  48.         nxt_k += ( a[x][y] == '(' ? 1 : -1) ;
  49.         if(nxt_k > k || nxt_k < 0 ) break ;
  50.  
  51.         if(nxt_k == 0  ) cur = add(cur, 1 ) ;
  52.         ll nxt_dir = (cur_dir + 1 ) % 4 ;
  53.         ll nxt_x = x + dx[nxt_dir ], nxt_y = y + dy[nxt_dir ] ;
  54.  
  55.         if(in(nxt_x, nxt_y, lim_left, lim_top, lim_right, lim_bot )) {
  56.             if(nxt_dir == 1 ) cur = add(cur, DP(lim_left, x , y + 1 , lim_bot, nxt_k, nxt_dir  ) ) ;
  57.             if(nxt_dir == 2 ) cur = add(cur, DP(lim_left, lim_top, y  , x + 1  , nxt_k, nxt_dir  ) ) ;
  58.             if(nxt_dir == 3 ) cur = add(cur, DP(y - 1 , lim_top, lim_right, x , nxt_k, nxt_dir  ) ) ;
  59.             if(nxt_dir == 0 ) cur = add(cur, DP(y , x - 1, lim_right, lim_bot, nxt_k, nxt_dir  ) ) ;
  60.  
  61.         }
  62.  
  63.         x += dx[cur_dir ] ;
  64.         y += dy[cur_dir ] ;
  65.  
  66.     }
  67.     return cur ;
  68. }
  69.  
  70. void init() {
  71.     cin >> n >> m >> k ;
  72.     FOR(i, 1, n ) FOR(j, 1, m ) cin >> a[i][j] ;
  73. }
  74.  
  75. void solve() {
  76.     memset(dp, - 1, sizeof dp ) ;
  77.     cout << DP(0, 0, m + 1, n + 1, 0, 0 ) ;
  78. }
  79.  
  80. _ROOT_ {
  81.     // freopen(NAME".inp" , "r" , stdin);
  82.     // freopen(NAME".out" , "w", stdout) ;
  83.     ios_base::sync_with_stdio(0);
  84.     cin.tie(0);
  85.     cout.tie(0);
  86.     int t = 1; // cin >> t ;
  87.     while(t--) {
  88.         init();
  89.         solve();
  90.     }
  91.     return (0&0);
  92. }
  93.  
Success #stdin #stdout 0.02s 162252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/CxlzOY
language:
C++14 (gcc 8.3)
created:
7 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!