Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include<bits/stdc++.h>

using namespace std;

#define rep(i,n) for(i = 0; i<n; i++)
#define repl(i,n) for(i = 1; i<=n; i++)

#define sz(x)   (int)x.size()
#define pb      push_back
#define all(x)  x.begin(),e.end()
#define uu      first
#define vv  second
#define mem(x,y) memset(x,y,sizeof(x))
#define sdi(x) scanf("%d",&x)
#define sdii(x,y) scanf("%d %d",&x,&y)
#define sdiii(x,y,z)  scanf("%d %d %d",&x,&y,&z)
#define sdl(x) scanf("%lld",&x)
#define sdll(x,y) scanf("%lld %lld",&x,&y)
#define sdlll(x,y,z)  scanf("%lld %lld %lld",&x,&y,&z)
#define sds(x) scanf("%s",s);
#define pfi(x) printf("%d\n",x)
#define pfii(x,y) printf("%d %d\n",x,y)
#define pfiii(x,y,z) printf("%d %d %d\n",x,y,z)
#define pfl(x) printf("%lld\n",x)
#define pfll(x,y) printf("%lld %lld\n",x,y)
#define pflll(x,y,z) printf("%lld %lld %lld\n",x,y,z)

#define eps 1e-9
#define OK  cerr<< "OK" << '\n'
#define DB(x) cerr << #x " = " << x << '\n'

#define FRE(i,a,b) for(i = a; i<=b; i++)
#define FRL(i,a,b) for(i = a; i<b; i++)
#define un(x) x.erase(unique(all(x)),x.end())
#define sf(x) scanf("%d",&x)
#define sff(x,y) scanf("%d %d",&x,&y)
#define sfff(x,y,z)  scanf("%d %d %d",&x,&y,&z)
#define sl(x) scanf("%lld",&x)
#define sll(x,y) scanf("%lld %lld",&x,&y)
#define slll(x,y,z)  scanf("%lld %lld %lld",&x,&y,&z)
#define D(x)        cerr << #x " = " << x << '\n'
#define DBG         cerr << "Hi" << '\n'
#define PI          acose(-1.00)
#define xx          first
#define yy          second

typedef double db;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;

inline int setBit(int N, int pos) { return N=N|(1<<pos);}
inline int resetBit(int N, int pos) {return N=N &~(1<<pos);}
inline bool checkBit(int N, int pos) {return (bool) (N & (1<<pos));}


 int fx[] = {+0, +0, +1, -1, +1, -1, +1};
 int fy[] = {-1, +1, +0, +0, +1, -1, -1};

#define MAX         200

int R, C;
char A[MAX+10][MAX+10];
queue<pii> q;
int distSol[MAX+10][MAX+10];
bool vis[MAX+10][MAX+10];

bool ok(pii a)
{
    if(a.xx >= 0 && a.xx <R && a.yy >= 0 && a.yy < C)
        return true;
    return false;
}

void bfs()
{
    while(!q.empty())
    {
        pii nw = q.front();
        q.pop();
        for(int i = 0; i<4; i++)
        {
            pii tmp = nw;
            tmp.xx += fx[i];
            tmp.yy += fy[i];
            if(ok(tmp) && vis[tmp.xx][tmp.yy] == 0 && A[tmp.xx][tmp.yy] != '#')
            {
                distSol[tmp.xx][tmp.yy] = distSol[nw.xx][nw.yy] + 1;
                vis[tmp.xx][tmp.yy] = true;
                q.push(tmp);
            }
        }
    }
}

pii princess, dest;

int dist[MAX+10][MAX+10];
bool bfsPrincess()
{
    mem(vis,0);
    vis[princess.xx][princess.yy] = true;
    dist[princess.xx][princess.yy] = 0;
    q.push(princess);
    while(!q.empty())
    {
        pii nw = q.front();
        q.pop();
        for(int i = 0; i<4; i++)
        {
            pii tmp = nw;
            tmp.xx += fx[i];
            tmp.yy += fy[i];
            int cur = dist[nw.xx][nw.yy] + 1;
            if(ok(tmp) && vis[tmp.xx][tmp.yy] == 0 && A[tmp.xx][tmp.yy] != '#' && distSol[tmp.xx][tmp.yy] > cur)
            {
                dist[tmp.xx][tmp.yy] = cur;
                vis[tmp.xx][tmp.yy] = true;
                q.push(tmp);
            }
        }
    }
    if(vis[dest.xx][dest.yy])
        return true;
    return false;
}

int main()
{
    /// freopen("in.txt", "r", stdin);
    /// freopen("out.txt", "w", stdout);
    int i, j, cs, t;
    mem(distSol,63);
    sff(R,C);
    FRL(i,0,R)
        scanf("%s",A[i]);
    for(i = 0; i<R; i++)
    {
        for(j = 0; j<C; j++)
        {
            if(A[i][j] == '@')
                princess = {i,j};
            else if(A[i][j] == '%')
                dest = {i,j};
            else if(A[i][j] == '$')
                q.push({i,j}),vis[i][j] = true, distSol[i][j] = 0;
        }
    }
    bfs();
//    for(int i = 0; i<R; i++)
//    {
//        for(int j = 0; j<C; j++)
//            cout << distSol[i][j] << " " ;
//        cout << endl;
//    }
    if(bfsPrincess())
        printf("Yes\n");
    else
        printf("No\n");
    return 0;
}