MAGCARI

mew

Dec 26th, 2022
922
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.55 KB | None | 0 0
  1. /*
  2.     Task    : _example
  3.     Author  : Phumipat C. [MAGCARI]
  4.     Language: C++
  5.     Created : 26 December 2022 [18:26]
  6. */
  7. #include<bits/stdc++.h>
  8. using namespace std;
  9. const int N = 125;
  10. char a[N][N];
  11. int goodEnding[N][N][2];
  12. int n,m;
  13. void dfs(int i,int j,int dir){
  14.     // dir == 0 means left
  15.     // dir == 1 means right
  16.     if(goodEnding[i][j][dir])   return ;
  17.     // printf("%d %d %d\n",i,j,dir);
  18.     if(a[i][j] == '.'){
  19.         // falling
  20.         dfs(i+1,j,dir);
  21.         goodEnding[i][j][dir] = goodEnding[i+1][j][dir];
  22.     }else if(a[i][j] == '$'){
  23.         // treasure
  24.         goodEnding[i][j][dir] = 1;
  25.     }else if(a[i][j] == '@'){
  26.         // fail
  27.         goodEnding[i][j][dir] = -1;
  28.     }else{
  29.         // moving
  30.         if(dir == 0){
  31.             if(j == 1){
  32.                 dfs(i,j,1);
  33.                 goodEnding[i][j][dir] = goodEnding[i][j][1];
  34.             }else{
  35.                 dfs(i,j-1,0);
  36.                 goodEnding[i][j][dir] = goodEnding[i][j-1][0];
  37.             }
  38.         }else{
  39.             if(j == m){
  40.                 dfs(i,j,0);
  41.                 goodEnding[i][j][dir] = goodEnding[i][j][0];
  42.             }else{
  43.                 dfs(i,j+1,1);
  44.                 goodEnding[i][j][dir] = goodEnding[i][j+1][1];
  45.             }
  46.         }
  47.     }
  48. }
  49. int findTreasure(){
  50.     int cnt = 0;
  51.     memset(goodEnding,0,sizeof goodEnding);
  52.     for(int j=1;j<=m;j++){
  53.         dfs(1,j,0),dfs(1,j,1);
  54.         cnt+=(goodEnding[1][j][0] == 1) + (goodEnding[1][j][1] == 1);
  55.     }
  56.     return cnt;
  57. }
  58. int main(){
  59.     cin.tie(0)->sync_with_stdio(0);
  60.     cin.exceptions(cin.failbit);
  61.     cin >> m >> n;
  62.     for(int i=1;i<=n;i++)
  63.         cin >> a[i]+1;
  64.     cout << findTreasure() << ' ';
  65.     // able to destroy 1 floor
  66.     int mx = 0;
  67.     for(int i=1;i<n;i++){
  68.         for(int j=1;j<=m;j++){
  69.             if(a[i][j] == '.')  continue;
  70.             a[i][j] = '.';
  71.             mx = max(mx,findTreasure());
  72.             a[i][j] = '#';
  73.         }
  74.     }
  75.     cout << mx << '\n';
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment