链接：原题

题目

给你一个 $H\times W$ 的网格，称 $(i,j)$ 表示网格从上往下数第 $i$ 行，从左往右第 $j$ 行的格子。

每个格子要么是空地（用 ' $.$ ' 表示），要么是障碍物（用 ' # ' 表示）。

把一个棋子放在 $(1,1)$ 的位置，两个人（这两人此后简称 “ $First$ ” ," $Second$ "）轮流进行操作。

$First$ 先操作。

每次操作只能将棋子向下、右下、右这三个方向的其中一个移动一格。

移动最后一步棋的人获胜。

请问最终谁获胜？

题解

显然这是一个公平组合游戏，于是对于先手而言：

• 一个状态能通过一次转移，转移到必败态，那么这个状态是必胜态

• 一个状态通过一次转移，只能转移到必胜态，那么这个状态是必败态。

• 如果一个状态没有后继状态，那么这个状态是一个必败态。

考虑搜索整张图，然后在 $(1,1)$ 处得到答案。

如果把棋子初始放在 $(H,W)$ , 那么这个状态为必败。

然后由 $(H,W)$ 的状态，慢慢扩散回去。

对于一个位置 $(i,j)$ ，如果 $(i+1,j)\:,\:(i,j+1)\:,\:(i+1,j+1)$ 其中有一个是障碍物，那么我们就不用它们的结果扩展 $(i,j)$。

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18
const int N = 1000;
int dp[N][N];
char s[N][N];

void slove(){
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
         for (int j = 1; j <= m; j++) 
            cin >> s[i][j];
    
    dp[n][m] = -1;
    for (int i = n; i >= 1; i--)
        for(int j = m; j >= 1; j--) {
            if (i == n and j == m) continue;
            dp[i][j] = -1;
            if (i + 1 <= n and j + 1 <= m and dp[i + 1][j + 1] == -1 and s[i + 1][j + 1] == '.') dp[i][j] = 1;
            if (i + 1 <= n and dp[i + 1][j] == -1 and s[i + 1][j] == '.') dp[i][j] = 1;
            if (j + 1 <= m and dp[i][j + 1] == -1 and s[i][j + 1] == '.') dp[i][j] = 1;
        }

    int ans = dp[1][1];

    if (ans == -1) cout << "Second" << endl;
    else cout << "First" << endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    slove();
}