题目大意
在一个 \(n\times m\) 的网格中，存在红色和蓝色两种格子，红色格子用 - 表示，蓝色格子用 + 表示。
现在 Takahashi 和 Aoki 要在这个网格中进行游戏，游戏的规则如下：
- 初始时，有一枚棋子摆放在左上角，即 \((1,1)\) 的位置。两名玩家的分数均为 \(0\)。
- 双方轮流行动，Takahashi 先行动。
- 在每次行动中，行动者可以选择将棋子向下或向右移动一格，但移动后不能超出网格。移动后如果棋子位于红色格子，那么行动者的分数 \(-1\)，否则 \(+1\)。
- 当棋子无法行动时，即位于 \((n,m)\) 时，游戏结束，得分高者为胜者。
现在告诉你网格的颜色情况，请你判断谁将会获胜。你可以认为这两名玩家都绝顶聪明。
思路分析
在打 AT 时，一个重要的原则是遇事不决就 DP。
考虑 DP，设 \(f_{i,j}\) 表示棋子位于 \((i,j)\) 时，Takahashi 的得分与 Aoki 的得分的差。
那么 Takahashi 的目标是最大化这个值，而 Aoki 则想要最小化这个值。
因为棋子只能向右或向下走，所以此时的回合数就是 \(i+j-1\)（回合从 \(1\) 开始）。那么容易写出状态转移方程：
\[f_{i,j}=\begin{cases}\max(f_{i+1,j}+a_{i+1,j},f_{i,j+1}+a_{i,j+1})&i+j-1\equiv 1\pmod2\\\min(f_{i+1,j}-a_{i+1,j},f_{i,j+1}-a_{i,j+1})&i+j-1\equiv 0\pmod2\end{cases} \]（\(a_{i,j}\) 表示这一位的符号，即若 \((i,j)\) 为 +，那么 \(a_{i,j}\) 为 \(1\)，否则为 \(-1\)。）
因为转移比较奇怪，所以考虑用记搜实现。
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2020;
#define inf 0x3f3f3f3f
int a[N][N],dp[N][N];
int n,m;
char ch[N];
int dfs(int x,int y){
if(x==n&&y==m) return 0;//到达边界
if(dp[x][y]) return dp[x][y];
if((x+y-1)%2==1){
dp[x][y]=-inf;//记得赋初值和特判边界！
if(x!=n) dp[x][y]=max(dp[x][y],dfs(x+1,y)+a[x+1][y]);
if(y!=m) dp[x][y]=max(dp[x][y],dfs(x,y+1)+a[x][y+1]);
return dp[x][y];
}
else{
dp[x][y]=inf;
if(x!=n) dp[x][y]=min(dp[x][y],dfs(x+1,y)-a[x+1][y]);
if(y!=m) dp[x][y]=min(dp[x][y],dfs(x,y+1)-a[x][y+1]);
return dp[x][y];
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",ch+1);
for(int j=1;j<=m;j++)
a[i][j]=(ch[j]=='+')?1:-1;
}
int ans=dfs(1,1);//1 1 即为答案
if(ans>0) cout<<"Takahashi\n";
if(ans==0) cout<<"Draw\n";
if(ans<0) cout<<"Aoki\n";
return 0;
}