Problem: Example

Input

2 4
%.@\$
..\$\$


Output

Yes

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
struct P{
  int x,y,d;
  P(int y,int x,int d):y(y),x(x),d(d){}
};
int main(){
  int h,w;cin>>h>>w;
  int pr=1<<28,so=1<<28,i,j,k;
  char m[h+2][w+2];
  memset(m,'#',sizeof(m));
  P p=P(0,0,0);
  vector<P> ss;
  for(i=1;i<=h;i++){
    for(j=1;j<=w;j++){
      cin>>m[i][j];
      if(m[i][j]=='@') p.y=i,p.x=j,p.d=0;
      if(m[i][j]=='$') ss.push_back(P(i,j,0));
    }
  }
  queue<P> q;
  bool used[h+2][w+2];
  int ax[]={1,-1,0,0};
  int ay[]={0,0,1,-1};
  memset(used,0,sizeof(used));
  q.push(p);
  while(!q.empty()){
    p=q.front();q.pop();
    if(m[p.y][p.x]=='%') {
      pr=p.d;
      break;
    }
    if(used[p.y][p.x]) continue;
    used[p.y][p.x]=true;
    for(k=0;k<4;k++){
      if(m[p.y+ay[k]][p.x+ax[k]]!='#'&&!used[p.y+ay[k]][p.x+ax[k]])
	q.push(P(p.y+ay[k],p.x+ax[k],p.d+1));
    }
  }
  while(!q.empty()) q.pop();
  memset(used,0,sizeof(used));
  for(i=0;i<ss.size();i++) q.push(ss[i]);
  while(!q.empty()){
    p=q.front();q.pop();
    if(m[p.y][p.x]=='%') {
      so=p.d;
      break;
    }
    if(used[p.y][p.x]) continue;
    used[p.y][p.x]=true;
    for(k=0;k<4;k++){
      if(m[p.y+ay[k]][p.x+ax[k]]!='#'&&!used[p.y+ay[k]][p.x+ax[k]])
	q.push(P(p.y+ay[k],p.x+ax[k],p.d+1));
    }
  }
  //cout << pr << " " << so << endl;
  cout << ((pr<so)?"Yes":"No") << endl;
  return 0;
}