Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
#define INF 100000000
using namespace std;

struct state {
  int y, x, d;
  bool operator<(const state &s) const {
    return d > s.d;
  }
};

int H, W, SY, SX;
char S[300][300];
int dd[5] = { 0, 1, 0, -1, 0 };
bool visited[300][300];

bool isin(int y, int x) {
  return 0 <= y && y < H && 0 <= x && x < W;
}

int main(void) {
  cin >> H >> W;
  REP(i, 0, H) REP(j, 0, W) {
    cin >> S[i][j];
    if(S[i][j] == '%') {
      SY = i;
      SX = j;
    }
  }

  REP(i, 0, H) REP(j, 0, W) visited[i][j] = false;
  queue<state> q;
  q.push((state) { SY, SX, 0 });

  int d1 = INF, d2 = INF;
  while(q.size()) {
    state c = q.front();
    q.pop();
    if(visited[c.y][c.x]) continue;
    visited[c.y][c.x] = true;
    if(S[c.y][c.x] == '@') {
      d1 = c.d;
    }
    if(S[c.y][c.x] == '$') {
      d2 = min(d2, c.d);
    }
    REP(i, 0, 4) {
      int ny = c.y + dd[i], nx = c.x + dd[i + 1];
      if(isin(ny, nx) && S[ny][nx] != '#' && !visited[ny][nx]) {
        q.push((state) { ny, nx, c.d + 1 });
      }
    }
  }
  cout << (d1 < d2 ? "Yes" : "No") << endl;

  return 0;
}