弹珠游戏【牛客tracker 每日一题】
弹珠游戏
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
A l i c e AliceAlice对弹珠游戏已经有些厌烦了，她经常在电脑上玩这个游戏。她之所以感到厌烦是因为在这个游戏上她已经是专家级别，她总是能够和电脑打成平手。 B o b BobBob为 A l i c e AliceAlice创造了一款新的电脑游戏。以下是这款两人电脑游戏的规则：
1.游戏在如下图所示的菱形棋盘上进行；
2. 两名玩家轮流放置弹珠，可以在横向、纵向、45 4545度斜线、135 135135度斜线方向未放置弹珠的位置连续放置1 11至3 33颗弹珠，玩家在可以放置弹珠的情况下，必须至少放置1 11颗弹珠。以下是合法的单次放置操作的示例（黑色圆点表示放置了弹珠，白色圆点表示未放置弹珠，进行该次操作前棋盘为空）：
以下是非法的单次放置操作的示例（黑色圆点表示放置了弹珠，白色圆点表示未放置弹珠，进行该次操作前棋盘为空）：
非法原因的解释：（a aa）三颗弹珠不在同一条斜线（或者垂直线）上；（b bb）两颗弹珠之间相隔一个空位；（c cc）三颗弹珠不在同一条斜线上；（d dd）三颗弹珠不在同一条斜线（或者垂直线）上；（e ee）一次性放置了4 44颗弹珠；（f ff）三颗弹珠不在同一条水平线（或者垂直线、或者斜线）上。
3. 如果某位玩家无法再继续放置弹珠，则该名玩家输掉游戏，另外一名玩家获胜。
A l i c e AliceAlice总是第一个进行游戏，而且经常是和 B o b BobBob玩这个游戏，B o b BobBob在进行若干游戏操作后可能会离开，将游戏交由电脑代理，电脑总是按照最优策略放置弹珠。
给定B o b BobBob离开后的游戏状态，你的任务是确定A l i c e AliceAlice是否可能在对阵电脑时获得胜利。
输入描述：
每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≦ T ≦ 200 ) T(1≦T≦200)T(1≦T≦200)代表数据组数，每组测试数据描述如下：
一共七行，每行输入一个字符串，表示B o b BobBob离开后的游戏状态。字符串的长度依次为1 , 2 , 3 , 4 , 3 , 2 , 1 1,2,3,4,3,2,11,2,3,4,3,2,1，且仅由‘ ∗ ’ ‘*’‘∗’和‘ . ’ ‘.’‘.’构成。‘ ∗ ’ ‘*’‘∗’表示该位置已经放置了弹珠，‘ . ’ ‘.’‘.’表示该位置未放置弹珠。
除此之外，每组测试文件间使用一个空行间隔。
输出描述：
对于每组测试数据，如果A l i c e AliceAlice能够获胜，输出A l i c e AliceAlice，否则输出 B o b BobBob。
示例1
输入：
6 * * * * * * * * * * . * * . * . * * * * * * . . . * * * * * * * * * * * * . * * * * * * . * * * * * * . . * * * * * * * * * * * . * * * * * * * * . * * * * * * . * . * * . * * * . * * * * * *输出：
Alice Alice Alice Alice Bob Alice说明：
第一组数据， A l i c e AliceAlice可以选择在棋盘左下角的斜线方向所剩下的3 33个空余位置一次性连续放置3 33颗弹珠，使得后续电脑无法再放置弹珠，因此A l i c e AliceAlice能够获胜。
第二组数据，A l i c e AliceAlice可以选择沿着第四行剩下的3 33个空余位置一次性连续放置3 33颗弹珠，使得后续电脑无法再放置弹珠，因此A l i c e AliceAlice能够获胜。
第三组数据，棋盘剩下倒数第二列两个连续的空余位置， A l i c e AliceAlice可以一次放置2 22颗弹珠，使得后续电脑无法放置弹珠，因此A l i c e AliceAlice会获胜。
第四组数据，类似于第二组测试数据，棋盘剩下第三行两个连续的空余位置，因此A l i c e AliceAlice会获胜。
第五组数据，棋盘只剩下两个不连续的空余位置，由于 A l i c e AliceAlice一次只能选择一个空余位置放置1 11颗弹珠，因此不管A l i c e AliceAlice如何操作，电脑总能一次性将剩下的棋盘使用弹珠填满，使得A l i c e AliceAlice无法再继续放置弹珠，因此 A l i c e AliceAlice会输掉比赛。
第六组数据，A l i c e AliceAlice可以选择在棋盘右上角斜线方向的中间两个空余位置放置2 22颗弹珠，使得棋盘状态转化为样例输入的第五组数据，因此A l i c e AliceAlice会赢得比赛。
解题思路
本题核心是博弈论+记忆化搜索，判定菱形棋盘上先手A l i c e AliceAlice是否必胜。将不规则菱形棋盘映射为4 × 4 4×44×4标准网格，简化坐标遍历。采用胜负态规则：无空位可放弹珠时当前玩家败；若存在任意合法操作（横/竖/45 ° 45°45°/135 ° 135°135°斜线连续放1 − 3 1-31−3颗弹珠）使对手进入败态，则当前态为胜态。使用哈希表记忆化存储棋盘状态，避免重复递归计算。遍历所有合法操作，递归判断后续状态，最终确定当前状态的胜负，输出对应结果。算法通过坐标映射与记忆化剪枝，高效处理多组测试数据，精准匹配游戏规则。
总结
核心逻辑：博弈论胜负态判定，先手存在必胜操作则A l i c e AliceAlice胜，否则B o b BobBob胜。
关键操作：菱形棋盘转4 × 4 4×44×4网格、枚举四方向连续1 − 3 1-31−3个合法放置、记忆化存储状态。
效率保障：记忆化搜索剪枝，避免重复计算，高效处理题目约束的测试数据规模。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;map<vector<string>,ll>vsl;llfind(vector<string>s){if(vsl.count(s))returnvsl[s];ll ans=0;for(ll i=0;i<4;i++)for(ll j=0;j<4;j++){if(s[i][j]=='.')ans++;}if(ans==0){returnvsl[s]=-1;}for(ll i=0;i<4;i++){for(ll j=0;j<4;j++){if(s[i][j]=='.'){vector<string>vs=s;for(ll p=i;p<min(4ll,i+3);p++){if(vs[p][j]=='.'){vs[p][j]='*';if(find(vs)==-1){returnvsl[s]=1;}}elsebreak;}vs=s;for(ll p=j;p<min(j+3,4ll);p++){if(vs[i][p]=='.'){vs[i][p]='*';if(find(vs)==-1){returnvsl[s]=1;}}elsebreak;}vs=s;for(ll p=i,q=j;p<min(4ll,i+3)&&q<min(4ll,j+3);p++,q++){if(vs[p][q]=='.'){vs[p][q]='*';if(find(vs)==-1){returnvsl[s]=1;}}elsebreak;}vs=s;for(ll p=i,q=j;p<min(4ll,i+3)&&q>max(-1ll,j-3);p++,q--){if(vs[p][q]=='.'){vs[p][q]='*';if(find(vs)==-1){returnvsl[s]=1;}}elsebreak;}}}}returnvsl[s]=-1;}intmain(){ll t;cin>>t;vector<pll>vp={{0,0},{1,0},{0,1},{2,0},{1,1},{0,2},{3,0},{2,1},{1,2},{0,3},{3,1},{2,2},{1,3},{3,2},{2,3},{3,3}};while(t--){vector<string>s(4,"....");for(ll i=0;i<16;i++){ll x=vp[i].first;ll y=vp[i].second;charp;cin>>p;s[x][y]=p;}ll ans=find(s);if(ans==1)cout<<"Alice"<<endl;elsecout<<"Bob"<<endl;}return0;}