Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};

int d[210][210];

bool isOutOfRange(int y, int x, int h, int w){
	return y < 0 || y >= h || x < 0 || x >= w;
}

int main(){
	int h, w;
	cin>>h>>w;
	vector<string> vs(h);
	rep(i, h) cin>>vs[i];

	vector<pii> v;
	pii s, g;
	rep(i, h) rep(j, w) if(vs[i][j] == '$') v.pb({i, j});
	rep(i, h) rep(j, w) if(vs[i][j] == '@') s = {i, j};
	rep(i, h) rep(j, w) if(vs[i][j] == '%') g = {i, j};

	rep(i, 210) rep(j, 210) d[i][j] = INF;
	rep(i, v.size()){
		queue<pii> q;
		q.push(v[i]);
		d[v[i].fi][v[i].se] = 0;
		while(!q.empty()){
			pii p = q.front();	q.pop();
			int c = d[p.fi][p.se];
			rep(j, 4){
				int nx = p.se + dx[j], ny = p.fi + dy[j];
				if(isOutOfRange(ny, nx, h, w) || vs[ny][nx] == '#') continue;
				int nc = d[ny][nx];
				if(c+1 < nc){
					d[ny][nx] = c + 1;
					q.push({ny, nx});
				}
			}
		}
	}
	priority_queue<pair<int, pii>, vector<pair<int, pii> > , greater<pair<int, pii> > > q;
	pair<int, pii> p;
	set<pii> used;
	q.push({0, s});
	used.insert(s);
	while(!q.empty()){
		p = q.top(); q.pop();
		int c = p.fi;
		//cout<<" "<<p.se.fi<<" "<<p.se.se<<" "<<p.fi<<endl;
		rep(i, 4){
			int nx = p.se.se + dx[i], ny = p.se.fi + dy[i];
			if(isOutOfRange(ny, nx, h, w) || vs[ny][nx] == '#') continue;
			int nc = d[ny][nx];
			if(nc <= c+1 || used.count({ny, nx})) continue;
			if(g == (pii){ny, nx}){
				cout<<"Yes"<<endl;
				return 0;
			}
			q.push({c+1, {ny, nx}});
			used.insert({ny, nx});
		}
	}
	cout<<"No"<<endl;

	// for(int i = 0; i < h; i++){
	// 	for(int j = 0; j < w; j++){
	// 		printf("%3d", (d[i][j]==INF?-1:d[i][j]));
	// 	}
	// 	printf("\n");
	// }
}