Submission #22651166

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main() {
  int H, W;
  cin >> H >> W;

  vector<vector<char> > A(H, vector<char>(W));
  for(int i=0;i<H;i++) {
    for(int j=0;j<W;j++) {
      cin >> A[i][j];
    }
  }

  vector<vector<long long> > dp(H, vector<long long>(W, 0));

  for(int i=H-1;i>=0;i--) {
    for(int j=W-1;j>=0;j--) {
      if(i == H-1 && j == W-1) continue;

      if((i+j) % 2 == 1) {
        // Aokiがうつ
        int tmp1 = 10000000, tmp2 = 10000000;
        if(j != W - 1) {
          if(A[i][j+1] == '-') tmp1 = dp[i][j+1] + 1;
          if(A[i][j+1] == '+') tmp1 = dp[i][j+1] - 1;
        }
        if(i != H - 1) {
          if(A[i+1][j] == '-') tmp2 = dp[i+1][j] + 1;
          if(A[i+1][j] == '+') tmp2 = dp[i+1][j] - 1;
        }

        dp[i][j] = min(tmp1, tmp2);
      } 
      if((i+j) % 2 == 0) {
        int tmp1 = -10000000, tmp2 = -10000000;
        // Takahashiがうつ
        if(j != W - 1) {
          if(A[i][j+1] == '-') tmp1 = dp[i][j+1] - 1;
          if(A[i][j+1] == '+') tmp1 = dp[i][j+1] + 1;
        }
        if(i != H - 1) {
          if(A[i+1][j] == '-') tmp2 = dp[i+1][j] - 1;
          if(A[i+1][j] == '+') tmp2 = dp[i+1][j] + 1;
        }

        dp[i][j] = max(tmp1, tmp2);

      }
    }
  }

  if(dp[0][0] == 0) cout << "Draw" << endl;
  if(dp[0][0] > 0)  cout << "Takahashi" << endl;
  if(dp[0][0] < 0)  cout << "Aoki" << endl;
}

Submission Info

Judge Result