Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Task : _example
- Author : Phumipat C. [MAGCARI]
- Language: C++
- Created : 26 December 2022 [18:26]
- */
- #include<bits/stdc++.h>
- using namespace std;
- const int N = 125;
- char a[N][N];
- int goodEnding[N][N][2];
- int n,m;
- void dfs(int i,int j,int dir){
- // dir == 0 means left
- // dir == 1 means right
- if(goodEnding[i][j][dir]) return ;
- // printf("%d %d %d\n",i,j,dir);
- if(a[i][j] == '.'){
- // falling
- dfs(i+1,j,dir);
- goodEnding[i][j][dir] = goodEnding[i+1][j][dir];
- }else if(a[i][j] == '$'){
- // treasure
- goodEnding[i][j][dir] = 1;
- }else if(a[i][j] == '@'){
- // fail
- goodEnding[i][j][dir] = -1;
- }else{
- // moving
- if(dir == 0){
- if(j == 1){
- dfs(i,j,1);
- goodEnding[i][j][dir] = goodEnding[i][j][1];
- }else{
- dfs(i,j-1,0);
- goodEnding[i][j][dir] = goodEnding[i][j-1][0];
- }
- }else{
- if(j == m){
- dfs(i,j,0);
- goodEnding[i][j][dir] = goodEnding[i][j][0];
- }else{
- dfs(i,j+1,1);
- goodEnding[i][j][dir] = goodEnding[i][j+1][1];
- }
- }
- }
- }
- int findTreasure(){
- int cnt = 0;
- memset(goodEnding,0,sizeof goodEnding);
- for(int j=1;j<=m;j++){
- dfs(1,j,0),dfs(1,j,1);
- cnt+=(goodEnding[1][j][0] == 1) + (goodEnding[1][j][1] == 1);
- }
- return cnt;
- }
- int main(){
- cin.tie(0)->sync_with_stdio(0);
- cin.exceptions(cin.failbit);
- cin >> m >> n;
- for(int i=1;i<=n;i++)
- cin >> a[i]+1;
- cout << findTreasure() << ' ';
- // able to destroy 1 floor
- int mx = 0;
- for(int i=1;i<n;i++){
- for(int j=1;j<=m;j++){
- if(a[i][j] == '.') continue;
- a[i][j] = '.';
- mx = max(mx,findTreasure());
- a[i][j] = '#';
- }
- }
- cout << mx << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment