Submission #20191654

---

Source Code Expand

#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = 3.14159265359;
const ll INF = 1LL << 60;

int h, w;

// 0: not determined, 1: First win, -1: Second win.
int dp[100][100];

vector<string> g;

int judge(int y, int x){
  if (dp[y][x] != 0) return dp[y][x];

  vector<int> dx { 0, 1, 1};
  vector<int> dy { 1, 1, 0};
  for (int i = 0; i < 3; i++){
    int yy = y + dy[i];
    int xx = x + dx[i];
    dp[y][x] = 0;
    if (yy < h && xx < w && g[yy][xx] != '#'){
      int r =judge(yy, xx);
      if (r == 0) return (dp[y][x] = 1);
    }
  }
  return dp[y][x];
}

int main()
{
  cin >> h >> w;
  g.resize(h);
  for (string& t : g) cin >> t;

  int ans = judge(0, 0);
  if (ans == 1){
    cout << "First" << endl;
  } else {
    cout << "Second" << endl;
  }
  return 0;
}

Submission Info

Judge Result