Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
#include<queue>
#include<iostream>
#include<vector>
#include<string>
#include<set>
using namespace std;
typedef pair<int, int> pii;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};
 
bool isRange(int nx, int ny, int w, int h){
  return (0 <= nx and nx < w and
          0 <= ny and ny < h);
}
 
void bfs(queue<vector<int> > &que, vector<vector<int> > &dist , vector<string> &grid){
  int h = dist.size(), w = dist[0].size();
  while(not que.empty()){
    int c = que.front()[0];
    int x = que.front()[1];
    int y = que.front()[2];
    que.pop();
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i], ny = y + dy[i];
      if(not isRange(nx, ny, w, h))continue;
      if(c + 1 >= dist[ny][nx])continue;
      if(grid[ny][nx] == '#')continue;
      dist[ny][nx] = c + 1;
      que.push(vector<int>{c + 1, nx, ny});
    }
  }
}
 
int main(){
  int h, w;
  std::cin >> h >> w;
  vector<string> grid(h);
  pii s, g;
  set<pii> e;
  vector<vector<int> > dist_p(h, vector<int>(w, 1e9));
  vector<vector<int> > dist_e(h, vector<int>(w, 1e9));
  for (int i = 0; i < h; i++) {
    std::cin >> grid[i];
    for (int j = 0; j < w; j++) {
      if(grid[i][j] == '%')g = pii(j, i);
      if(grid[i][j] == '@')s = pii(j, i);
      if(grid[i][j] == '$')e.insert(pii(j, i));
    }
  }
  queue<vector<int> > que;
  que.push(vector<int>{0, s.first, s.second});
  dist_p[s.second][s.first] = 0;
  bfs(que, dist_p, grid);
 
  for (auto pos: e){
    dist_e[pos.second][pos.first] = 0;
    que.push(vector<int>{0, pos.first, pos.second});
  }
  bfs(que, dist_e, grid);
  
  que.push(vector<int>{0, s.first, s.second});
  vector< vector<bool> > visited(h, vector<bool>(w,false));
  visited[s.second][s.first] = true;
  while(not que.empty()){
    int c = que.front()[0];
    int x = que.front()[1];
    int y = que.front()[2];
    que.pop();
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i], ny = y + dy[i];
      if(not isRange(nx, ny, w, h))continue;
      if(dist_p[ny][nx] >= dist_e[ny][nx])continue;
      if(grid[ny][nx] == '#')continue;
      if(visited[ny][nx])continue;
      visited[ny][nx] = true;
      que.push(vector<int>{c + 1, nx, ny});
    }
  }
  std::cout << ((visited[g.second][g.first])?"Yes":"No") << std::endl;
  return 0;
}