Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <cfloat>

using std::cerr;
using std::cin;
using std::cout;
using std::endl;

typedef std::pair<int,int> P;

struct State{
  int depth;
  int r,c;
  State(int pr,int pc,int d):r(pr),c(pc),depth(d){}
};

int main(){
  cout << std::fixed << std::setprecision(16);
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int h,w;
  cin>>h>>w;
  char map[202][202]={};

  P princess;
  P goal;
  std::vector<P> soldier;

  for(int c=0;c<=w+1;c++){
    map[0][c]='#';
    map[h+1][c]='#';
  }



  for(int r=1;r<=h;r++){
    std::string s;
    cin>>s;
    map[r][0]='#';
    for(int c=1;c<=w;c++){
      map[r][c]=s[c-1];
      if(map[r][c]=='@'){
        princess=std::make_pair(r,c);
      }else if(map[r][c]=='$'){
        soldier.push_back(std::make_pair(r,c));
      }else if(map[r][c]=='%'){
        goal = std::make_pair(r, c);
      }
    }
    map[r][w+1]='#';
  }

  bool p_visited[202][202]={};
  p_visited[princess.first][princess.second]=true;

  int princess_turn=0;
  std::queue<State> q;
  q.push(State(princess.first,princess.second,0));
  while(!q.empty()){
    State curr=q.front();
    q.pop();
    if(map[curr.r][curr.c]=='%'){
      princess_turn=curr.depth;
      break;
    }
    for(int vr=-1;vr<=1;vr++){
      for(int vc=-1;vc<=1;vc++){

        if(!((vr==0&&vc!=0)||(vc==0&&vr!=0))){
          continue;
        }

        if(map[curr.r+vr][curr.c+vc]!='#'&&!p_visited[curr.r+vr][curr.c+vc]){
          p_visited[curr.r+vr][curr.c+vc]=true;
          q.push(State(curr.r+vr,curr.c+vc,curr.depth+1));
        }

      }
    }
  }

  int min_turn=INT32_MAX/3;



    std::queue<State> sq;

    bool visited[202][202]={};
    visited[goal.first][goal.second]=true;

    int turn=INT32_MAX/3;
    sq.push(State(goal.first,goal.second,0));
    while(!sq.empty()){
      State curr=sq.front();
      sq.pop();
      if(map[curr.r][curr.c]=='$'){
        turn=curr.depth;
        break;
      }
      for(int vr=-1;vr<=1;vr++){
        for(int vc=-1;vc<=1;vc++){

          if(!((vr==0&&vc!=0)||(vc==0&&vr!=0))){
            continue;
          }

          if(map[curr.r+vr][curr.c+vc]!='#'&&!visited[curr.r+vr][curr.c+vc]){
            visited[curr.r+vr][curr.c+vc]=true;
            sq.push(State(curr.r+vr,curr.c+vc,curr.depth+1));
          }

        }
      }
    }

    min_turn=std::min(min_turn,turn);


  cout<<((princess_turn<min_turn)?"Yes":"No")<<endl;








  return 0;
}