Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;
using ld = long double;
const ld eps = 1e-9;

//// < "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\a.txt" > "d:\d_download\visual studio 2015\projects\programing_contest_c++\debug\b.txt"

struct aa {
	int x;
	int y;
	int time;
};


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

int prx, pry;
int hax, hay;
int dfs(const vector<vector<int>>&field, vector<vector<int>>&memo) {

	queue<aa>que;
	que.push(aa{ prx,pry,0 });
	while (!que.empty()) {
		aa atop(que.front());
		if (atop.y == hay&&atop.x == hax)return atop.time;
		que.pop();
		for (int way = 0; way < 4; ++way) {
			const int nextx = atop.x + dx[way];
			const int nexty = atop.y + dy[way];
			const int nexttime = atop.time + 1;
			if (field[nexty][nextx] > nexttime) {

				if (memo[nexty][nextx]>nexttime) {
					memo[nexty][nextx] = nexttime;
					que.push(aa{ nextx,nexty,nexttime });
				}
			}
		}
	}
	return -1;
}

int main() {
	int H, W; cin >> H >> W;
	vector<vector<int>>field(H + 2, vector<int>(W + 2, -1));
	vector<vector<int>>memo(H + 2, vector<int>(W + 2, 1000));

	queue<aa>que;
	for (int i = 0; i < H; ++i) {
		string st; cin >> st;
		for (int j = 0; j < W; ++j) {
			char ch = st[j];
			if (ch == '@') {
				prx = j + 1, pry = i + 1;
				field[i+1][j+1] = 1000;
			}
			else if (ch == '%') {
				hax = j + 1, hay = i + 1;
				field[i + 1][j + 1] = 1000;
			}
			else if (ch == '$') {
				que.push(aa{ j + 1,i + 1,0 });
				field[i + 1][j + 1] = 0;
			}
			else if (ch == '.') {
				field[i + 1][j + 1] = 1000;
			}
			else {
				field[i + 1][j + 1] = -1;
			}
		}
	}
	memo[pry][prx] = 0;
	while (!que.empty()) {
		aa atop(que.front());
		que.pop();
		for (int way = 0; way < 4; ++way) {
			const int nextx = atop.x + dx[way];
			const int nexty = atop.y + dy[way];
			const int nexttime = atop.time + 1;
			if (field[nexty][nextx] >= 0) {

				if (field[nexty][nextx]>nexttime) {
					field[nexty][nextx] = nexttime;
					que.push(aa{ nextx,nexty,nexttime });
				}
			}
		}
	}
	int ans = dfs(field, memo);
	if (ans >= 0)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}