Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include "bits/stdc++.h"
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> T;
int h,w;
int dx[5]={1,0,-1,0,0};
int dy[5]={0,-1,0,1,0};
bool fail[5001][200][200]; //iターン目で兵士のいる可能性のある場所
int mincost[200][200];
deque<T> q;

int main()
{
	vector<string> mp;
	cin>>h>>w;
	for(int i=0;i<h;i++)
	{
		string s;
		cin>>s;
		mp.push_back(s);
	}
	bool ans=false;
	fill(fail[0][0],fail[5001][0],false);
	fill(mincost[0],mincost[200],1e8-1);
	//初期配置を定める
	for(int i=0;i<h;i++)
	{
		for(int j=0;j<w;j++)
		{
			if(mp[i][j]=='$')
				fail[0][i][j]=true;
			if(mp[i][j]=='@')
			{
				q.push_back(T(0,P(i,j)));
				mincost[i][j]=0;
			}
		}
	}
	//兵士の移動パターンをすべて調べる
	for(int k=1;k<1001;k++)
	{
		for(int i=0;i<h;i++)
		{
			for(int j=0;j<w;j++)
			{
				if(fail[k-1][i][j])
				{
					for(int l=0;l<5;l++)
					{
						int nx=i+dx[l];
						int ny=j+dy[l];
						if(nx>=0 && nx<h && ny>=0 && ny<w && mp[nx][ny]!='#')
							fail[k][nx][ny]=true;
					}
				}
			}
		}
	}
	// for(int i=0;i<h;i++)
	// {
	// 	for(int j=0;j<w;j++)
	// 	{
	// 		if(fail[1000][i][j])
	// 			cout<<'$';
	// 		else
	// 			cout<<mp[i][j];
	// 	}
	// 	cout<<endl;
	// }
	//BFS
	while(!q.empty())
	{
		T t=q.front();q.pop_front();
		P p=t.second;
		if(t.first==1000)
			continue;
		if(mp[p.first][p.second]=='%')
		{
			ans=true;
			break;
		}
		for(int i=0;i<4;i++)
		{
			int nx=p.first+dx[i];
			int ny=p.second+dy[i];
			if(nx>=0 && nx<h && ny>=0 && ny<w && mp[nx][ny]!='#')
			{
				if(!fail[t.first+1][nx][ny] && mincost[nx][ny]==1e8-1)
				{
					q.push_back(T(t.first+1,P(nx,ny)));
					mincost[nx][ny]=t.first+1;
				}
			}
		}
	}
	if(ans)
		cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
	return 0;
}