Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
using P = pair<int,int>;

int main(){
    int H,W;
    cin>>H>>W;
    int map[H][W];
    P princess;
    vector<P> soldier;
    for(int i=0;i<H;i++){
        for(int j=0;j<W;j++){
            char c;
            cin>>c;
            map[i][j]=1;
            if(c=='#') map[i][j]=0;
            if(c=='%') map[i][j]=2;
            if(c=='@') princess=P(j,i);
            if(c=='$') soldier.emplace_back(j,i);
        }
    }
    if(!soldier.size()){
        cout<<"Yes"<<endl;
        return 0;
    }
    int dist[H][W];
    queue<P> Q;
    Q.push(princess);
    fill(dist[0],dist[H],100000000);
    int dist_princess=-1;
    dist[get<1>(princess)][get<0>(princess)]=0;
    while(!Q.empty()){
        int x,y;
        tie(x,y)=Q.front(); Q.pop();
        if(map[y][x]==2){
            dist_princess=dist[y][x];
            while(!Q.empty()) Q.pop();
            break;
        }
        int d[5]={0,1,0,-1,0};
        for(int k=0;k<4;k++){
            int dx=d[k],dy=d[k+1];
            if(x+dx<0||W<=x+dx||y+dy<0||H<=y+dy) continue;
            if(map[y+dy][x+dx]){
                if(dist[y+dy][x+dx]>dist[y][x]+1){
                    Q.push(P(x+dx,y+dy));
                    dist[y+dy][x+dx]=dist[y][x]+1;
                }
            }
        }
    }
    int dist_soldier=100000000;
    fill(dist[0],dist[H],100000000);
    for(auto s:soldier){
        Q.push(s);
        dist[get<1>(s)][get<0>(s)]=0;
    }
    while(!Q.empty()){
        int x,y;
        tie(x,y)=Q.front(); Q.pop();
        if(map[y][x]==2){
            dist_soldier=dist[y][x];
            break;
        }
        int d[5]={0,1,0,-1,0};
        for(int k=0;k<4;k++){
            int dx=d[k],dy=d[k+1];
            if(x+dx<0||W<=x+dx||y+dy<0||H<=y+dy) continue;
            if(map[y+dy][x+dx]){
                if(dist[y+dy][x+dx]>dist[y][x]+1){
                    Q.push(P(x+dx,y+dy));
                    dist[y+dy][x+dx]=dist[y][x]+1;
                }
            }
        }
    }
    // cout<<dist_princess<<' '<<dist_soldier<<endl;
    if(dist_soldier<=dist_princess){
        cout<<"No"<<endl;
    }else{
        cout<<"Yes"<<endl;
    }
}