Problem: Example

Input

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


Output

Yes

Solution (in CPP):

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

using namespace std;
typedef long long ll;

struct P {
  int y, x;
  P() {}
  P(int y, int x) : y(y), x(x) {}
};

int h, w;
vector<string> s;
P start, goal;
vector<P> demons;
int dy[] = {-1, 0, 0, 1}, dx[] = {0, -1, 1, 0};

void bfs(vector<vector<int>>& d, vector<P> v) {
  queue<pair<P, int>> que;
  for (int i = 0; i < v.size(); i++) {
    d[v[i].y][v[i].x] = 0;
    que.push({v[i], 0});
  }
  while (que.size()) {
    auto p = que.front(); que.pop();
    int py = p.first.y, px = p.first.x;
    for (int i = 0; i < 4; i++) {
      int ny = py + dy[i], nx = px + dx[i];
      if (ny >= 0 && ny < h && nx >= 0 && nx < w && s[ny][nx] != '#' && d[ny][nx] > d[py][px] + 1) {
        d[ny][nx] = d[py][px] + 1;
        que.push({{ny, nx}, d[ny][nx]});
      }
    }
  }
}

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  
  cin >> h >> w;
  s.resize(h);
  for (int i = 0; i < h; i++) {
    cin >> s[i];
    for (int j = 0; j < w; j++) {
      if (s[i][j] == '@') start = {i, j};
      else if (s[i][j] == '%') goal = {i, j};
      else if (s[i][j] == '$') demons.emplace_back(i, j);
    }
  }

  vector<vector<int>> d1(h, vector<int>(w, 1 << 30)), d2 = d1;
  vector<P> tmp(1, start);
  bfs(d1, tmp);
  bfs(d2, demons);
  cout << (d1[goal.y][goal.x] < d2[goal.y][goal.x] ? "Yes" : "No") << endl;

  return 0;
}