Submission #2329144

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

int a, b, w, h;
vector<string> m;
int memo[16][16][16][16][4];

bool dfs(int x, int y, int aa, int bb, int d) {
  if (memo[x][y][aa][bb][d] != -1) return memo[x][y][aa][bb][d];
  if (x == w-2 && y == h-2 && aa == 0 && bb == 0)
    return memo[x][y][aa][bb][d] = true;
  bool r = false;

  {
    int nx = x + dx[d], ny = y + dy[d];
    if (m[ny][nx] == '.')
      r |= dfs(nx, ny, aa, bb, d);
  }
  if (aa > 0) {
    int nd = (d+3)%4;
    int nx = x + dx[nd], ny = y + dy[nd];
    if (m[ny][nx] == '.')
      r |= dfs(nx, ny, aa-1, bb, nd);
  }
  if (bb > 0) { // L
    int nd = (d+1)%4;
    int nx = x + dx[nd], ny = y + dy[nd];
    if (m[ny][nx] == '.')
      r |= dfs(nx, ny, aa, bb-1, nd);
  }

  return memo[x][y][aa][bb][d] = r;
}

int main() {
  cin >> a >> b >> h >> w;
  m = vector<string>(h);
  for (int i=0; i<h; i++) cin >> m[i];
  for (int i=0; i<16; i++)
    for (int j=0; j<16; j++)
      for (int u=0; u<16; u++)
        for (int v=0; v<16; v++)
          for (int k=0; k<4; k++)
            memo[i][j][u][v][k] = -1;
  cout << (dfs(1, 1, a, b, 1) ? "Yes" : "No") << endl;
  return 0;
}

Submission Info

Judge Result