题解 | 弹珠游戏

因为一共16个弹珠位，每个位置两种可能，一共有2^16=65536种，状态记忆化搜索加减枝枚举各个状态
然后这个棱形映射成正方形更方便搜索
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
int pos[16][2]={
	{1,1},
	{2,1},{1,2},
	{3,1},{2,2},{1,3},
	{4,1},{3,2},{2,3},{1,4},
	{4,2},{3,3},{2,4},
	{4,3},{3,4},
	{4,4}
};
int dirs[4][2]={
	{1,0},{0,1},{1,1},{1,-1}
};
unordered_map<string,int> st;
int deal(string ts)
{
	if(st.count(ts)) return st[ts];
	int count=0;
	for(int i=0;i<16;i++)
	{
		if(ts[i]=='.')
		{
			count++;
		}
	}
	if(count==0) return st[ts]=-1;
	for(int i=0;i<16;i++)
	{
		int x=i/4+1,y=i%4+1;
		if(ts[i]=='*') continue;
		for(int j=0;j<4;j++)
		{
			int dx=dirs[j][0],dy=dirs[j][1];
			string tts=ts;
			for(int step=0;step<3;step++)
			{
				int cux=x+step*dx,cuy=y+step*dy;
				if(cux<1||cuy<1||cux>4||cuy>4) break;
				int id=(cux-1)*4+cuy-1;
				if(ts[id]=='*') break;
				else tts[id]='*';
				if(deal(tts)==-1)
				{
					return st[ts]=1;
				}
			}
		}
	}
	return st[ts]=-1;
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--)
	{
		st.clear();
		string ss;
		for(int i=0;i<16;i++)
		{
			char s;
			cin>>s;
			ss+=s;
		}
		string ts(16,' ');
	    //先转化成正方形
		for(int i=0;i<16;i++)
		{
			int tx=pos[i][1],ty=pos[i][0];
			int id=(tx-1)*4+ty-1;
			ts[id]=ss[i];
		}
		if(deal(ts)==1) cout<<"Alice"<<endl;
		else cout<<"Bob"<<endl;
	}
	return 0;
}