Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

//幅優先探索
//迷路の最短距離を求める
//まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
//次に、それぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。
//スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。

// queue (FIFO) を使うのがスマート(atcoder調べ)
// pop() := キューの先頭要素を削除
// front() 先頭要素の参照
// push() := キューの末尾にデータを追加
// 出し入れするデータは座標

// 入力例
// 7 8
// 2 2
// 4 5
// ########
// #......#
// #.######
// #..#...#
// #..##..#
// ##.....#
// ########

// 出力例
// 11

int di[4] = {0, -1, 0, 1};
int dj[4] = {1, 0, -1, 0};

int main(){

    //入力
    int r, c, si, sj, gi, gj;
    cin >> r >> c;
    
    queue<pair<int, int> > p[2];
    queue<pair<int, int> > s[2];
    
    // canGo[i][j] := (i, j) が壁ならばfalse, 通路ならばtrue
    vector<vector<bool> > canGo(r + 2, vector<bool> (c + 2, false));
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            char input; cin >> input;
            if(input == '#') continue;
            else if(input == '$'){
                s[0].push({i, j});
            }else{
                canGo[i][j] = true;

                if(input == '@'){
                    //canGo[i][j] = false;
                    p[0].push({i, j});
                }else if(input == '%'){
                    gi = i;
                    gj = j;
                }

            }
        }
    }

    //cout << gi << " " << gj << endl;

    int now = 0;

    while(!p[now].empty()){

        //兵士動いてください
        //cout << "soldier" << endl;
        while(!s[now].empty()){

            int nowi = s[now].front().first;
            int nowj = s[now].front().second;
            
            //cout << nowi << " " << nowj << endl;

            s[now].pop();
            if(nowi == gi && nowj == gj){
                cout << "No" << endl;
                return 0;
            }

            //四方向を探索
            for(int k = 0; k < 4; k++){
                int nexti = nowi + di[k];
                int nextj = nowj + dj[k];

                //その方向に進めるなら
                if(canGo[nexti][nextj]){
                    //そのマスにキューを追加し
                    //再度検索することのないように壁で埋める
                    s[(now + 1) % 2].push({nexti, nextj});
                    canGo[nexti][nextj] = false;
                }
            }
        }

        //cout << endl;

        //姫さんどうぞ
        //cout << "princess" << endl;
        while(!p[now].empty()){    //キュー画空になるまで
            //キューの先頭要素を取り出す
            //int nowcost = wait.front().first;
            int nowi = p[now].front().first;
            int nowj = p[now].front().second;

            //cout << nowi << " " << nowj << endl;

            p[now].pop();

            //ゴールにたどり着いたらそのコストが答え
            if(nowi == gi && nowj == gj){
                cout << "Yes" << endl;
                return 0;
            }

            //四方向を探索
            for(int k = 0; k < 4; k++){
                int nexti = nowi + di[k];
                int nextj = nowj + dj[k];

                //その方向に進めるなら
                if(canGo[nexti][nextj]){
                    //そのマスにキューを追加し
                    //再度検索することのないように壁で埋める
                    p[(now + 1) % 2].push({nexti, nextj});                    
                    canGo[nexti][nextj] = false;
                }
            }
        }

        now = (now + 1) % 2;

    }
    
    cout << "No" << endl;
    return 0;

}