Submission #36906603

---

Source Code Expand

#include <bits/stdc++.h>

#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define int long long

using namespace std;

const int N = 2e3+5;
int dp[N][N], grid[N][N];

signed main(){
	fastio
	int n,m;
	cin >> n >> m;
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			char c;
			cin >> c;
			if(c == '+') grid[i][j] = 1;
			else grid[i][j] = -1;
		}
	}

	for(int i = n; i >= 1; i--){
		for(int j = m; j >= 1; j--){
			if(i == n && j == m) dp[i][j] = 0;
			else if(i == n) dp[i][j] = dp[i][j+1];
			else if(j == m) dp[i][j] = dp[i+1][j];
			else{
				if((i+j)%2) dp[i][j] = min(dp[i][j+1],dp[i+1][j]);
				else dp[i][j] = max(dp[i][j+1],dp[i+1][j]);
			}
			if(i == 1 && j == 1) continue;
			dp[i][j] += ((i+j)%2 ? 1 : -1) * grid[i][j];
		}
	}

	if(dp[1][1] > 0) cout << "Takahashi\n";
	else if(dp[1][1] == 0) cout << "Draw\n";
	else cout << "Aoki\n";
}

Submission Info

Judge Result