526互联

AtCoder Beginner Contest 201 D - Game in Momotetsu World

发布时间 2023-09-01 22:46:51作者: 无上大宗师

D - Game in Momotetsu World


原题链接


题意
有一个 H×W 的方格，每个方格里写着 '+' 或 '-'
有一个初始在 (1,1),（也就是左上角)的棋子，
Takahashi 和 Aoki 轮流向右或向下移动（Takahashi 先手）。
移动到写着 '+' 的方格上后，进行该步移动的玩家分数 +1。
否则该玩家分数 −1，走到右下角后游戏结束。
问双方都进行最佳操作时，哪一方获胜？


思路：i+j为偶数格子时是Aoki走，奇数时Takahashi走，都按各自的最优走法走


#include <bits/stdc++.h>
using namespace std;
const int N = 2010;
int f[N][N],g[N][N];//f[i][j]=T得分-A得分
char tmp[N][N];

int main()
{
	int n,m;
	cin>>n>>m;
	
	for(int i=0;i<n;i++)//0~n-1 0~m-1的方格
	{
		cin>>tmp[i];
		for(int j=0;j<m;j++)
		{
			g[i][j]= tmp[i][j]=='+'? 1:-1;//价值
		}
	}
	
	//初始化
	f[n-1][m-1]=0;
	for(int j=m-2;j>=0;j--)
	{
		if((j+n-1)%2==0)//(i+j)为偶数,即T走路来获取分数
		{
			f[n-1][j]=f[n-1][j+1]+g[n-1][j+1];
		}
		else
		{
			f[n-1][j]=f[n-1][j+1]-g[n-1][j+1];
		}
	}
	for(int i=n-2;i>=0;i--)
	{
		if((i+m-1)%2==0)
		{
			f[i][m-1]=f[i+1][m-1]+g[i+1][m-1];
		}
		else
		{
			f[i][m-1]=f[i+1][m-1]-g[i+1][m-1];
		}
	}


	for(int i=n-2;i>=0;i--)
	{
		for(int j=m-2;j>=0;j--)
		{
			if((i+j)%2==0)//
			{
				f[i][j]=max(f[i+1][j]+g[i+1][j],f[i][j+1]+g[i][j+1]);
			}
			else
			{
				f[i][j]=min(f[i+1][j]-g[i+1][j],f[i][j+1]-g[i][j+1]);//各自按照最优策略走
			}
		}
	}

	if(f[0][0]>0) cout<<"Takahashi\n";
	else if(f[0][0]<0) cout<<"Aoki\n";
	else cout<<"Draw\n";
	//cout<<f[0][0]<<'\n';
}