Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

struct edge
{
	int to;
	long long cost;
	edge(int to_, long long cost_) :
		to(to_), cost(cost_) {}
};
const long long INF = 123456789012345;
using P = pair<long long, int>;//first:cost,second:vertice
void dijkstra(vector<edge>graph_[], long long dist[], int n_, int s_)
{
	priority_queue<P, vector<P>, greater<P>>que;
	que.push({ 0,s_ });
	fill(dist, dist + n_, INF);
	dist[s_] = 0ll;
	while (!que.empty())
	{
		auto q = que.top();
		que.pop();
		long long thd = q.first;
		int thv = q.second;
		if (thd > dist[thv])
		{
			continue;
		}
		for (auto ed : graph_[thv])
		{
			if (dist[ed.to] > ed.cost + thd)
			{
				dist[ed.to] = ed.cost + thd;
				que.push({ dist[ed.to],ed.to });
			}
		}
	}
}


int h, w;
int g, p;
vector<int>sol;
vector<edge>graph[200 * 200];
LL dist[200 * 200];
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
int main()
{
	cin >> h >> w;
	for (int i = 0; i < h; ++i)
	{
		string s;
		cin >> s;
		for (int j = 0; j < w; ++j)
		{
			if (s[j] == '#')continue;
			for (int d = 0; d < 4; ++d)
			{
				int ii = i + dx[d];
				int jj = j + dy[d];
				if (ii < 0 || jj < 0 || ii >= h || jj >= w)continue;
				graph[i * w + j].push_back(edge(ii * w + jj, 1));
			}
			if (s[j] == '@')p = i * w + j;
			if (s[j] == '$')sol.push_back(i * w + j);
			if (s[j] == '%')g = i * w + j;
		}
	}
	dijkstra(graph, dist, h*w, g);
	LL shut = INT_MAX;
	for (int s : sol)
	{
		shut = min(shut, dist[s]);
	}
	if (shut > dist[p])
	{
		cout << "Yes\n";
	}
	else
	{
		cout << "No\n";
	}
}