CSES Graphs- Monsters (Help needed)

Блог пользователя lalalalaaa...

Автор lalalalaaa..., история, 6 лет назад, По-английски

I have started solving some problems related to graphs and most of the times i am not able to pass the testcases, either it is TLE or WA. I was solving MONSTERS question from cses Problem Link and was unable to figure to out why some testcases gave TLE.

What i have done-

Applied bfs and stored the min distance between each cell and the monster (M) cell. Applied bfs for A and check whether there was a cell which was having less distance/ or more closer to A than any other M cell. And then checked whether it can reach to any border cell.

Link to My Code

It will be very helpful if anyone can let me know where i am going wrong.

#graphs, #bfs

lalalalaaa...
6 лет назад
9

Комментарии (6)

Показать архивные | Написать комментарий?

sia

6 лет назад, скрыть # |

← Rev. 3 →

You can check this, I have used bfs
CODE_LINK

CODE

#include<bits/stdc++.h>
#define ar array
using namespace std ;
const int mxN =1e3+2,di[4]={1,0,-1,0},dj[4]={0,1,0,-1};
const char dc[4]={'D','R','U','L'} ;
int n,m,si,sj,d1[mxN][mxN],d2[mxN][mxN],p1[mxN][mxN],p2[mxN][mxN] ;
bool vis[mxN][mxN] ;
string s[mxN] ;
bool e(int i,int j){
  return (i<n&&i>=0&&j<m&&j>=0&&s[i][j]=='.'&&!vis[i][j]);  
}
void bfs(vector<ar<int,2>>v1,int d[mxN][mxN],int p[mxN][mxN]){
  queue<ar<int,2>>qu  ;
  memset(vis,0,sizeof(vis)) ;
  memset(d,0x3f,sizeof(d1)) ;
  for(ar<int,2>a :v1){
    qu.push(a) ;
    vis[a[0]][a[1]]=1 ;
    d[a[0]][a[1]]=0 ;
  }  
  while(qu.size()){
    ar<int,2>u = qu.front();
    qu.pop() ;
    for(int k=0;k<4;k++){
      int ni=u[0]+di[k],nj=u[1]+dj[k] ;
      if(!e(ni,nj))
        continue ;
      qu.push({ni,nj});
      vis[ni][nj]=1 ;
      d[ni][nj]=d[u[0]][u[1]]+1 ;
      p[ni][nj]=k ;
    }
  }
}
signed main() {
  cin >> n >> m ;
  vector<ar<int,2>>v2 ;
  for(int i=0;i<n;i++){
    cin >> s[i] ;
    for(int j=0;j<m;j++){
      if(s[i][j]=='M')
        v2.push_back({i,j}),s[i][j]='.' ;
      if(s[i][j]=='A')
        si=i,sj=j,s[i][j]='.' ;
    }
  }
  bfs({{si,sj}},d1,p1);
  bfs(v2,d2,p2);
  int ti=-1,tj;
  for(int i=0;i<n;i++){
    if(d1[i][0]<d2[i][0])
      ti=i,tj=0 ;
    if(d1[i][m-1]<d2[i][m-1])
      ti=i,tj=m-1 ;
  }
  for(int j=0;j<m;j++){
    if(d1[0][j]<d2[0][j])
      ti=0,tj=j ;
    if(d1[n-1][j]<d2[n-1][j])
      ti=n-1,tj=j ;
  }
  if(~ti){
    string t ;
    cout << "YES\n" ;
    while(ti^si || tj^sj){
      t+=dc[p1[ti][tj]] ;
      int dd= (p1[ti][tj]^2) ;
      ti+=di[dd];tj+=dj[dd] ;
    }
    reverse(t.begin(),t.end());
    cout << t.size() << '\n' ;
    cout <<t << '\n' ;
  }else
    cout << "NO" << '\n' ;
}

→ Ответить

MasterMind

6 лет назад, скрыть # |

Hint

→ Ответить

lalalalaaa...

6 лет назад, скрыть # ^ |

← Rev. 2 →

I have applied multisource bfs only, but 4 testcases were giving TLE. My Code Sorry for the late reply

→ Ответить

MasterMind

6 лет назад, скрыть # ^ |

I have not looked through your code thoroughly, I can see problems in your functions, it is never a good idea to pass vector to a function by value, this would copy the entire vector, rather you should pass by reference.

→ Ответить

yash30201

6 лет назад, скрыть # |

Hi there,

Sorry haven't thought about the exact error in your code but I will state why I was getting WA and TLE

The reason for TLE was the case when your character is already at a border cell and the reason for WA was due to >= instead of just > when comparing distance during bfs from your cell.

→ Ответить