Problem: Example

Input

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


Output

Yes

Solution (in CPP):

Solution:
/*  -*- coding: utf-8 -*-
 *
 * 2781.cc: Help the Princess!
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_H = 200;
const int MAX_W = 200;
const int INF = 1 << 30;

const int dxs[] = { 1, 0, -1, 0 }, dys[] = { 0, -1, 0, 1 };

/* typedef */

typedef pair<int,int> pii;
typedef queue<pii> qpii;

/* global variables */

char flds[MAX_H][MAX_W + 4];
int dists[MAX_H][MAX_W];

/* subroutines */

bool bfs(qpii &q, int gx, int gy, int h, int w) {
  while (! q.empty()) {
    pii u = q.front(); q.pop();
    int &ux = u.first, &uy = u.second;
    if (ux == gx && uy == gy) return true;

    int vd = dists[uy][ux] + 1;
    
    for (int di = 0; di < 4; di++) {
      int vx = ux + dxs[di], vy = uy + dys[di];
      if (vx >= 0 && vx < w && vy >= 0 && vy < h &&
	  flds[vy][vx] == '.' && dists[vy][vx] > vd) {
	dists[vy][vx] = vd;
	q.push(pii(vx, vy));
      }
    }
  }

  return false;
}

/* main */

int main() {
  int h, w;
  scanf("%d%d", &h, &w);

  int px, py, gx, gy;
  qpii q;

  for (int y = 0; y < h; y++) {
    scanf("%s", flds[y]);
    fill(dists[y], dists[y] + w, INF);
    for (int x = 0; x < w; x++)
      switch (flds[y][x]) {
      case '@': px = x, py = y, flds[y][x] = '.'; break;
      case '%': gx = x, gy = y, flds[y][x] = '.'; break;
      case '$': q.push(pii(x, y)), dists[y][x] = 0, flds[y][x] = '.'; break;
      }
  }

  bfs(q, -1, -1, h, w);
  //for (int y = 0; y < h; y++) {
  //for (int x = 0; x < w; x++) printf("%d ", dists[y][x]);
  //putchar('\n');
  //}

  dists[py][px] = 0;
  q.push(pii(px, py));
  bool ok = bfs(q, gx, gy, h, w);
  if (ok) puts("Yes");
  else puts("No");
  return 0;
}