问题描述

有一个二维网格，并且某些单元格不可移动。
第一块在左上方的单元格中。
第一帧和第二帧交替移动。

轮到您，您可以将棋子移动到右，右下或下（可移动）相邻的正方形中的任何一个。
如果没有可移动的相邻方块，则玩家输。
如果双方都拿出最好的手，哪个是赢家？

问题分析

一个典型的两人完美信息游戏问题。
在记忆的递归和DP等中，从右下开始按以下方式确定获胜者。

• 无论您向右，向右下方或向左移动的位置，获胜（对手）的单元格都是失败的单元格。

• 在任一位置（右或右下或左或左）丢失的单元是获胜单元。

核心部分伪$Code$

int H,W;
string S[1010];
int memo[200][200];

int win(int Y,int X){
	
	int& ret=memo[Y][X];
	if(ret>=0) return ret;
	ret=0;
	
	if(Y<H-1 && S[Y+1][X]=='.' && win(Y+1,X)==0) ret=1;
	if(X<W-1 && S[Y][X+1]=='.' && win(Y,X+1)==0) ret=1;
	if(Y<H-1 && X<W-1 && S[Y+1][X+1]=='.' && win(Y+1,X+1)==0) ret=1;
	
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(memo);
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	
	if(win(0,0)) cout<<"First"<<endl;
	else cout<<"Second"<<endl;
}