Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main () {
  cin.tie(0);
  cout << fixed << setprecision(10);

  int h, w; cin>>h>>w;
  vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
  vector<vector<char>> a(h, vector<char>(w));
  pair<int, int> s, e;
  map<pair<int, int>, bool> enemy;
  map<pair<int, int>, bool> wall;
  for(int i=0;i<h;++i) {
    for(int j=0;j<w;++j) {
      cin >> a[i][j];
      pair<int, int> p = make_pair(i, j);
      if(a[i][j] == '@') s = p;
      else if(a[i][j] == '%') e = p;
      else if(a[i][j] == '$') enemy[p] = true;
      else if(a[i][j] == '#') wall[p] = true;
    }
  }

  vector<vector<int>> d(h, vector<int>(w, INF));
  queue<pair<int, int>> q;
  map<pair<int, int>, bool> sel;
  q.push(s);
  sel[s] = true;
  d[s.first][s.second] = 0;
  while(!q.empty()) {
    pair<int, int> now = q.front(); q.pop();
    // cout << now.first << ":" << now.second << endl;
    for(int i=0;i<4;++i) {
      pair<int, int> next = make_pair(now.first + dy[i], now.second + dx[i]);
      if(0 <= next.first && next.first < h && 0 <= next.second && next.second < w && !wall[next] && !sel[next]) {
        q.push(next);
        sel[next] = true;
        d[next.first][next.second] = d[now.first][now.second] + 1;
      }
    }
  }

  int d_prin = d[e.first][e.second];
  int d_enemy = INF;

  vector<vector<int>> de(h, vector<int>(w, INF));
  map<pair<int, int>, bool> sele;
  q.push(e);
  sele[e] = true;
  de[e.first][e.second] = 0;
  while(!q.empty()) {
    pair<int, int> now = q.front(); q.pop();
    if(enemy[now]) {
      d_enemy = de[now.first][now.second];
      break;
    }
    for(int i=0;i<4;++i) {
      pair<int, int> next = make_pair(now.first + dy[i], now.second + dx[i]);
      if(0 <= next.first && next.first < h && 0 <= next.second && next.second < w && !wall[next] && !sele[next]) {
        q.push(next);
        sele[next] = true;
        de[next.first][next.second] = de[now.first][now.second] + 1;
      }
    }
  }

  // cout << d_prin << ":" << d_enemy << endl;
  if(d_prin < d_enemy) cout << "Yes" << endl;
  else cout << "No" << endl;
  
}