Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

#define REP(i,a,b) for(int i=int(a);i<int(b);i++)

using namespace std;

typedef long long int lli;

struct Data {
    int x, y, c;
    Data(int x, int y, int c) : x(x), y(y), c(c) {}
};

int main () {
    int H, W;
    cin >> H >> W;
    queue<Data> q;
    queue<Data> s;
    int gx, gy;
    vector<vector<char>> ml(H + 2, vector<char>(W + 2, '#'));
    REP (i, 1, H + 1) REP (j, 1, W + 1) {
        cin >> ml[i][j];
        if (ml[i][j] == '@') {
            q.emplace(j, i, 0);
        }
        else if (ml[i][j] == '%') {
            gy = i;
            gx = j;
        }
        else if (ml[i][j] == '$') {
            s.emplace(j, i, 0);
        }
    }
    const int inf = 1 << 30;
    const int dx[4] = {0, 1, 0, -1};
    const int dy[4] = {1, 0, -1, 0};
    vector<vector<int>> pml(H + 2, vector<int>(W + 2, inf / 2));
    vector<vector<int>> sml(H + 2, vector<int>(W + 2, inf));

    auto func = [&ml, &dx, &dy](vector<vector<int>> &ps, queue<Data> &q) -> void {
        while (q.size()) {
            auto d = q.front();
            q.pop();
            if (ps[d.y][d.x] <= d.c) continue;
            ps[d.y][d.x] = d.c;
            REP (k, 0, 4) {
                int nx = d.x + dx[k];
                int ny = d.y + dy[k];
                if (ml[ny][nx] == '#') continue;
                q.emplace(nx, ny, d.c + 1);
            }
        }
    };
    func(pml, q);
    func(sml, s);
    cout << (pml[gy][gx] < sml[gy][gx] ? "Yes" : "No") << endl;
    return 0;
}