Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
#define double long double
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;

int h, w, sx, sy, gx, gy;
char c[210][210];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
bool used[210][210];

bool in(int x, int y){
    return 0<=x && x<h && 0<=y && y<w && c[x][y] != '#';
}

vector<vector<int>> bfs(vector<pii> &init){
    vector<vector<int>> d(h, vector<int>(w, MAX));
    queue<pii> que;
    for(auto &p: init){
        d[p.fi][p.se] = 0;
        que.push(p);
    }
    while(!que.empty()){
        int x, y;
        tie(x, y) = que.front(); que.pop();
        rep(i, 4){
            int nx = x+dx[i], ny = y+dy[i];
            if(in(nx, ny) && d[nx][ny] == MAX){
                d[nx][ny] = d[x][y] + 1;
                que.emplace(nx, ny);
            }
        }
    }
    return d;
}

void dfs(int x, int y){
    if(used[x][y]) return;
    used[x][y] = true;
    rep(i, 4){
        int nx = x+dx[i], ny=y+dy[i];
        if(in(nx, ny)) dfs(nx, ny);
    }
}

int main(){
    scanf("%d%d", &h, &w);
    rep(i, h)rep(j, w){
        scanf(" %c", &c[i][j]);
        if(c[i][j] == '@') sx = i, sy = j;
        if(c[i][j] == '%') gx = i, gy = j;
    }
    vector<pii> init;
    init.emplace_back(sx, sy);
    auto d_pr = bfs(init);
    init.clear();
    rep(i, h)rep(j, w)if(c[i][j] == '$') init.emplace_back(i, j);
    auto d_sl = bfs(init);

    rep(i, h)rep(j, w)if(d_pr[i][j] >= d_sl[i][j]) c[i][j] = '#';
    rep(i, h)rep(j, w) used[i][j] = false;
    dfs(sx, sy);
    puts(used[gx][gy] ? "Yes" : "No");
}