Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define INF (1e9)
#define H 205
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;

priority_queue<P1,vector<P1>,greater<P1> > q;
int h,w,sy,sx;
string s[H];
int d[H][H];

int dijkstra(){
  int dy[4]={-1,0,1,0};
  int dx[4]={0,1,0,-1};
  while(!q.empty()){
    P1 t=q.top(); q.pop();
    int y=t.second.first;
    int x=t.second.second;
    int cost=t.first;
    if(d[y][x]<cost)continue;
    if(s[y][x]=='%')return cost;
    for(int i=0;i<4;i++){
      int ny=y+dy[i],nx=x+dx[i];
      if(ny<0||nx<0||h<=ny||w<=nx)continue;
      if(s[ny][nx]=='#')continue;
      if(d[ny][nx]>cost+1){
	d[ny][nx]=cost+1;
	q.push(P1(cost+1,P(ny,nx)));
      }
    }
  }
  return INF;
}

int main(){
  cin>>h>>w;
  for(int i=0;i<h;i++){
    cin>>s[i];
    for(int j=0;j<w;j++){
      d[i][j]=INF;
      if(s[i][j]=='@')sy=i,sx=j;
      if(s[i][j]=='$'){
	q.push(P1(0,P(i,j)));
	d[i][j]=0;
      }
    }
  }
  int comp=dijkstra();
  while(!q.empty())q.pop();
  for(int i=0;i<h;i++)
    for(int j=0;j<w;j++)
      d[i][j]=INF;
  q.push(P1(0,P(sy,sx)));
  d[sy][sx]=0;
  int r=dijkstra();
  if(r<comp)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}