Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
constexpr long long MAX = 5100000;
constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
constexpr long long mod = 1000000007LL;
//constexpr long long mod = 998244353LL;
const long double PI = acos((long double)(-1));

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

vector<vector<int>> GridBFS(int sh, int sw, vector<string>& vs) {
	int dh[] = { 1,-1,0,0 };
	int dw[] = { 0,0,1,-1 };
	int H = vs.size();
	int W = vs[0].size();
	queue<pair<int, int>> q;
	vector<vector<int>> d(H, vector<int>(W, inf));
	q.emplace(sh, sw);
	d[sh][sw] = 0;
	while (!q.empty()) {
		int h, w; tie(h, w) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nh = h + dh[i];
			int nw = w + dw[i];
			if (nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
			if (vs[nh][nw] == '#') continue;
			if (chmin(d[nh][nw], d[h][w] + 1)) q.emplace(nh, nw);
		}
	}
	return d;
}

vector<vector<int>> MultiGridBFS(vector<int> &sh, vector<int> &sw, vector<string>& vs) {
	int dh[] = { 1,-1,0,0 };
	int dw[] = { 0,0,1,-1 };
	int H = vs.size();
	int W = vs[0].size();
	queue<pair<int, int>> q;
	vector<vector<int>> d(H, vector<int>(W, inf));
	for (int i = 0; i < sh.size(); i++) {
		d[sh[i]][sw[i]] = 0;
		q.emplace(sh[i], sw[i]);
	}
	while (!q.empty()) {
		int h, w; tie(h, w) = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nh = h + dh[i];
			int nw = w + dw[i];
			if (nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
			if (vs[nh][nw] == '#') continue;
			if (chmin(d[nh][nw], d[h][w] + 1)) q.emplace(nh, nw);
		}
	}
	return d;
}


int main()
{
	
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	
	int H, W; cin >> H >> W;
	vector<string> vs(H); for (int i = 0; i < H; i++) cin >> vs[i];
	int ph = -1, pw = -1, eh = -1, ew = -1;;
	vector<int> sh, sw;
	for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
		if (vs[i][j] == '$') sh.emplace_back(i), sw.emplace_back(j);
		if (vs[i][j] == '@') ph = i, pw = j;
		if (vs[i][j] == '%') eh = i, ew = j;
	}
	auto d1 = GridBFS(ph, pw, vs);
	auto d2 = MultiGridBFS(sh, sw, vs);
	if (d1[eh][ew] < d2[eh][ew]) cout << "Yes" << "\n";
	else cout << "No" << "\n";
	return 0;
}