Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
#define MAX 210
#define inf 1<<29
#define linf 1e18
#define eps (1e-8)
#define mod 1000000007
#define pi M_PI
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(),(a).end()
#define pd(a) printf("%.10f\n",(double)(a))
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,int> pdi;
typedef vector<int> vi;
typedef vector<pii> vpi;
const int dx[8]={1,0,-1,0,1,1,-1,-1};
const int dy[8]={0,1,0,-1,1,-1,1,-1};

int h,w;
string grid[MAX];
int mem1[MAX][MAX],mem2[MAX][MAX];

void init(){
  FOR(i,0,MAX){
    FOR(j,0,MAX){
      mem1[i][j]=inf;
      mem2[i][j]=inf;
    }
  }
}

bool in(int a,int b){
  if(a<0 || b<0 || h<=a || w<=b)return false;
  return true;
}

string solve(){
  queue<pii> q;
  FOR(i,0,h){
    FOR(j,0,w){
      if(grid[i][j]=='$'){
        q.push(mp(i,j));
        mem1[i][j]=0;
      }
    }
  }
  while(q.size()){
    pii u=q.front();
    q.pop();
    FOR(k,0,4){
      int ni=u.f+dy[k],nj=u.s+dx[k];
      if(!in(ni,nj))continue;
      if(grid[ni][nj]=='#')continue;
      if(mem1[u.f][u.s]+1<mem1[ni][nj]){
        mem1[ni][nj]=mem1[u.f][u.s]+1;
        q.push(mp(ni,nj));
      }
    }
  }
  FOR(i,0,h){
    FOR(j,0,w){
      if(grid[i][j]=='@'){
        q.push(mp(i,j));
        mem2[i][j]=0;
      }
    }
  }
  while(q.size()){
    pii u=q.front();
    q.pop();

    if(grid[u.f][u.s]=='%')return "Yes";

    FOR(k,0,4){
      int ni=u.f+dy[k],nj=u.s+dx[k];
      if(!in(ni,nj))continue;
      if(grid[ni][nj]=='#')continue;
      if(mem2[u.f][u.s]+1<mem2[ni][nj] && mem2[u.f][u.s]+1<mem1[ni][nj]){
        mem2[ni][nj]=mem2[u.f][u.s]+1;
        q.push(mp(ni,nj));
      }
    }
  }
  return "No";
}

int main()
{
  init();

  cin>>h>>w;
  FOR(i,0,h)cin>>grid[i];

  cout<<solve()<<endl;

  return 0;
}