正解其实是一个叫做：$Minimax$的算法。

可以去专门找点这样的题，你会发现是几乎类似的。

通常适用于两人博弈：

一人想要分数最大化（以下简称：“最大化棋手）。

另一人想要分数最小化（以下简称：“最小化棋手”）。

算法本质是通过搜索，找到所有路径，然后选择一条最优的路径。

朴素搜索的时间复杂度取决于搜索树的深度和分支。

一般是一个指数级别的时间复杂度，所以可以用记忆化搜索/评估函数估值剪枝的方法减少时间复杂度。

所以这就不奇怪为什么dp都是倒序了（搜索是自底而上的）。

因为本质上是用递推代替了搜索。

下面是代码：

#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

int h, w;
int a[3001][3001];
int flag[3001][3001];


int dfs(int x, int y,  bool isMax){ //坐标(x,y), 当前得分， 是否为最大化棋手

    //如果到达终点，返回。
    if (x == h and y == w) return 0;
    //如果这个点被遍历过，直接返回得到的结果
    if (flag[x][y]) return flag[x][y];

    int ans = 0;
    if (isMax) {
       ans = -INF;
       if (x + 1 <= h) ans = max(ans, dfs(x+1, y, false) + a[x+1][y]);
       if (y + 1 <= w) ans = max(ans, dfs(x, y+1, false) + a[x][y+1]);
    }
    else {
       ans = INF;
       if (x + 1 <= h) ans = min(ans, dfs(x+1, y, true) - a[x+1][y]);
       if (y + 1 <= w) ans = min(ans, dfs(x, y+1, true) - a[x][y+1]);
    }
    return flag[x][y] = ans;

}
void slove(){

   cin >> h >> w;
   for (int i = 1; i <= h; i++) {
       for (int j = 1; j <= w; j++) {
            char t;
            cin >> t;
            if (t == '+') a[i][j] = 1;
            else a[i][j] = -1;
       }
   }

   int ans = dfs(1, 1, true);

   if (ans > 0) cout << "Takahashi" << endl;
   else if (ans < 0) cout << "Aoki" << endl;
   else cout << "Draw" << endl;

}

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