Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include <queue>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int H, W;
int main() {
	cin >> H >> W;
	vector<string> v(H);
	for (int i = 0; i < H; i++) cin >> v[i];
	int N = H * W;
	vector<vector<int> > G(N);
	for (int i = 0; i < H - 1; i++) {
		for (int j = 0; j < W; j++) {
			if (v[i][j] == '#' || v[i + 1][j] == '#') continue;
			G[i * W + j].push_back(i * W + j + W);
			G[i * W + j + W].push_back(i * W + j);
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W - 1; j++) {
			if (v[i][j] == '#' || v[i][j + 1] == '#') continue;
			G[i * W + j].push_back(i * W + j + 1);
			G[i * W + j + 1].push_back(i * W + j);
		}
	}
	int s = -1, g = -1; vector<int> sol;
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (v[i][j] == '$') sol.push_back(i * W + j);
			if (v[i][j] == '@') s = i * W + j;
			if (v[i][j] == '%') g = i * W + j;
		}
	}
	vector<int> solt(N, 999999999);
	queue<int> que1;
	for (int i : sol) que1.push(i), solt[i] = 0;
	while (!que1.empty()) {
		int u = que1.front(); que1.pop();
		for (int i : G[u]) {
			if (solt[i] == 999999999) {
				solt[i] = solt[u] + 1;
				que1.push(i);
			}
		}
	}
	vector<int> dist(N, 999999999); dist[s] = 0;
	queue<int> que2; que2.push(s);
	while (!que2.empty()) {
		int u = que2.front(); que2.pop();
		for (int i : G[u]) {
			if (dist[i] == 999999999 && solt[i] > dist[u] + 1) {
				dist[i] = dist[u] + 1;
				que2.push(i);
			}
		}
	}
	cout << (dist[g] != 999999999 ? "Yes" : "No") << endl;
	return 0;
}