Problem: Example

Input

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


Output

Yes

Solution (in CPP):

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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef pair<int,int> ii;

int h,w,mini[210][210];
string s[210];
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};

void bfs(int sx,int sy) {
  rep(i,h) rep(j,w) mini[i][j] = INT_MAX;
  deque<ii> deq;
  deq.push_back(ii(sx,sy));
  mini[sy][sx] = 0;
  while( !deq.empty() ) {
    ii cur = deq.front(); deq.pop_front();
    rep(i,4) {
      int nx = cur.first  + dx[i];
      int ny = cur.second + dy[i];
      if( !( 0 <= nx && nx < w && 0 <= ny && ny < h) ) continue;
      if( s[ny][nx] == '#' ) continue;
      if( mini[ny][nx] > mini[cur.second][cur.first] + 1 ) {
        mini[ny][nx] = mini[cur.second][cur.first] + 1;
        deq.push_back(ii(nx,ny));
      }
    }
  }
}

void compute() {
  int sx=-1,sy, gx=-1,gy;
  vector<ii> vec;
  rep(i,h) rep(j,w) {
    if( s[i][j] == '@' ) sx = j, sy = i, s[i][j] = '.';
    if( s[i][j] == '%' ) gx = j, gy = i;
    if( s[i][j] == '$' ) vec.push_back(ii(j,i)), s[i][j] = '.';
  }
  bfs(gx,gy);
  if( mini[sy][sx] == INT_MAX ) {
    puts("No");
    return;
  }
  rep(i,(int)vec.size()) {
    ii tmp = vec[i];
    if( mini[sy][sx] >= mini[tmp.second][tmp.first] ) {
      puts("No");
      return;
    }
  }
  puts("Yes");
}

int main() {
  cin >> h >> w;
  rep(i,h) cin >> s[i];
  compute();
  return 0;
}