Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

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

struct UnionFind {
	vector<int> v;
	UnionFind(int n) : v(n) { for (int i = 0; i < n; i++) v[i] = i; }
	int  find(int x) { return v[x] == x ? x : v[x] = find(v[x]); }
	void unite(int x, int y) { v[find(x)] = find(y); }
};

int main() {
	int h, w;
	cin >> h >> w;
	vector<string> cells(h);
	vvi able(h, vi(w, 9999));
	REP(i, h)
		cin >> cells[i];
	int sx, sy, gx, gy;
	queue<pair<pii, int>> Qs;

	REP(i, h) {
		REP(j, w) {
			if (cells[i][j] == '@') {
				sx = j;
				sy = i;
			}
			if (cells[i][j] == '%') {
				gx = j;
				gy = i;
			}
			if (cells[i][j] == '$') {
				Qs.push({ {i,j},0 });
				able[i][j] = 0;
			}
			if (cells[i][j] == '#')
				continue;
		}
	}
	while (!Qs.empty())
	{
		pair<pii, int> q = Qs.front();
		Qs.pop();
		REP(k, 4) {
			int nx = q.first.second + dx[k];
			int ny = q.first.first + dy[k];
			if (0 <= ny&& ny < h && 0 <= nx && nx < w)
				if (cells[ny][nx] != '#')
					if (able[ny][nx] > q.second + 1) {
						able[ny][nx] = q.second + 1;
						Qs.push({ { ny,nx },q.second + 1 });
					}
		}
	}
	vvb visited(h, vb(w, false));
	visited[sy][sx] = true;
	queue<pair<pii, int>> Q;
	Q.push({{ sy,sx },0});
	bool ans = false;
	while (!Q.empty())
	{
		pair<pii, int> q = Q.front();
		Q.pop();
		if (q.first.first == gy&&q.first.second == gx) {
			ans = true;
			break;
		}
		REP(k, 4) {
			int nx = q.first.second + dx[k];
			int ny = q.first.first + dy[k];
			if (0 <= ny&& ny < h && 0 <= nx && nx < w)
				if (cells[ny][nx] != '#'&&able[ny][nx]>q.second+1)
					if (visited[ny][nx] == false) {
						visited[ny][nx] = true;
						Q.push({ { ny,nx },q.second+1 });
					}
		}
	}
	if (ans) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
}