本文最后更新于:2020年4月11日 下午

问题描述

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

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

问题分析

一个典型的两人完美信息游戏问题。
在记忆的递归和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;
}

本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

hexo博客【从0开始搭建自己的博客】 上一篇
题解 AT677 【おいらの素数生成式】 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。