75分的无脑解法QWQ
查看原帖
75分的无脑解法QWQ
749028
QAQ5楼主2025/1/5 16:20
#include<iostream>
/*创建坐标类型用来表示棋盘中的单元的位置,以左上角的一个单元为原点0,0,其左边为x轴正轴,下边为y轴正轴,但是输入数据中的坐标相比使用的坐标有偏差,所以要进行转换*/
struct position
{
	short x = -1, y = -1;
};
/*定义棋盘类型*/
struct checkerboard
{
	char surface[200][200] = { 0 };//棋盘表面
	position air;//空格位置
	bool inning = false;//谁的回合
};
/*多种情况的坐标*/
struct ps
{
	short n = 0;
	position p, pd[4];
};
/*将输入的外坐标转换为能直接使用的内坐标*/
position in(position to) {
	to.x--;
	to.y--;
	return to;
}
position size;
/*将方向转化为坐标*/
position dp(position center, short direction) {
	switch (direction) {
	case 0:
		if (center.y)
		{
			center.y--;
			return center;
		}
		break;
	case 1:
		if (center.y < size.y)
		{
			center.y++;
			return center;
		}
		break;
	case 2:
		if (center.x)
		{
			center.x--;
			return center;
		}
		break;
	case 3:
		if (center.x < size.x)
		{
			center.x++;
			return center;
		}
	}
	center.x = center.y = -1;
	return center;
}
/*以输入的坐标为中心查看上下左右中的某一个方向的单元是啥*/
char see(position center, short direction, checkerboard* source) {
	if ((center = dp(center, direction)).y >= 0)
		return source->surface[center.y][center.x];
	return 0;
}
/*以输入的坐标为中心向上下左右寻找输入的要寻找的单元*/
ps seek(position center, char need, checkerboard* source) {
	position p[4];
	short n = 0, i;
	for (i = 0; i < 4; i++)
		if (see(center, i, source) == need)
			p[n++] = dp(center, i);
	ps s;
	if (n > 0)
		if (n == 1)
		{
			s.n = 1;
			s.p = p[0];
		}
		else
		{
			s.n = n;
			for (i = 0; i < n; i++)
				s.pd[i] = p[i];
		}
	return s;
}
/*单步下棋,下棋的结果记录在新棋盘而保留旧的棋盘不变*/
checkerboard* tap(checkerboard* s, position play) {
	static checkerboard source;
	source = *s;
	source.surface[source.air.y][source.air.x] = source.surface[play.y][play.x];
	source.surface[play.y][play.x] = '.';
	source.air = play;
	source.inning = !source.inning;
	return &source;
}
int main() {
	using std::cin;
	using std::cout;
	using std::endl;
	register short i, index = 0, index2 = 0, num_of_error = 0;
	static short round, rounds, select[200] = { 0 }, round_of_error[200] = { 0 };
	cin >> size.y >> size.x;
	static checkerboard root, branch[200], cache;
	for (i = 0; i < size.y; i++)
		cin >> root.surface[i];
	cin >> round;
	rounds = round * 2;
	static position play[200];
	for (i = 0; i < rounds; i++)
		cin >> play[i].y >> play[i].x;
	//输入初始数据
	size = in(size);
	for (i = 0; i < rounds; i++)
		play[i] = in(play[i]);
	static ps h, z[200];
	h = seek(play[0], '.', &root);
	root.air = h.p;
	//初始数据初始化
	bool win;
	while (true)
	{//先判断白在下棋前白能否必胜,能胜才判断下一局黑能否必胜
		cache = root;
		while (true) {
			h = seek(cache.air, 'O', &cache);
			if (h.n)
				if (h.n == 1)
				{
					cache = *tap(&cache, h.p);
				g:
					h = seek(cache.air, 'X', &cache);
					if (h.n)
						if (h.n == 1)
							cache = *tap(&cache, h.p);
						else
						{
							branch[index] = cache, z[index] = h, select[index++] = 1;
							cache = *tap(&cache, h.pd[0]);
						}
					else//说明黑输了,这是白的回合预判,检查完所有情况黑都是输则白在这回合有必胜方法
					{
						if (index > 0)
						{
						cut1:
							if (index - 1)
							{
								if (!branch[index - 1].inning)
								{
									index--;
									goto cut1;
								}
							}
							else//如果已经截到最后一个分支
								if (!branch[0].inning)
								{
									win = true;//最后一个分支是白的,白必胜
									break;
								}
							if (select[index - 1] < z[index - 1].n)//这个黑分支
								cache = *tap(&branch[index - 1], z[index - 1].pd[select[index - 1]++]);//从这个黑回合的其它分支继续下棋检查
							else
								if (index - 1)//所有分支是否还没检查完毕
								{
									index--;//丢弃当前用完的分支继续检查
									goto cut1;
								}
								else
								{
									win = true;//检查到有无论黑怎么走都输的情况,白可以必胜
									break;//已经得出最终结论,终止计算
								}
						}
						else//如果没有分支,则白必胜
						{
							win = true;
							break;
						}
					}
				}
				else
				{
					branch[index] = cache, z[index] = h, select[index++] = 1;
					cache = *tap(&cache, h.pd[0]);
					goto g;
				}
			else//说明白输了,这是白的回合预判,检查白还有没有必胜的机会
			{
				if (index > 0)
				{
				cut0:
					if (index - 1)
					{
						if (branch[index - 1].inning)
						{
							index--;
							goto cut0;
						}
					}
					else//如果已经截到最后一个分支
						if (branch[0].inning)
						{
							win = false;//最后一个分支是黑的,黑必胜
							break;
						}
					if (select[index - 1] < z[index - 1].n)//这个白分支
					{
						cache = *tap(&branch[index - 1], z[index - 1].pd[select[index - 1]++]);//从这个白回合的其它分支继续下棋检查
						goto g;
					}
					else
						if (index - 1)//所有分支是否还没检查完毕
						{
							index--;//丢弃当前用完的分支继续检查
							goto cut0;
						}
						else
						{
							win = false;//检查到无论白怎么走都输,白无必胜方法
							break;//已经得出最终结论,终止计算
						}
				}
				else//如果没有分支,则白必输
				{
					win = false;
					break;
				}
			}
		}
		index = 0;
		if (win)
		{//已知白在上局有必胜方法,预判此局黑是否有必胜方法,预判方式没有区别但不好简化
			root = *tap(&root, play[index2++]);//下完这步后才是黑的回合
			cache = root;
			while (true) {
				h = seek(cache.air, 'X', &cache);
				if (h.n)
					if (h.n == 1)
					{
						cache = *tap(&cache, h.p);
					g2:
						h = seek(cache.air, 'O', &cache);
						if (h.n)
							if (h.n == 1)
								cache = *tap(&cache, h.p);
							else
							{
								branch[index] = cache, z[index] = h, select[index++] = 1;
								cache = *tap(&cache, h.pd[0]);
							}
						else//说明白输了,这是黑的回合预判,检查完所有情况白都是输则黑在这回合有必胜方法
						{
							if (index > 0)
							{
							cut02:
								if (index - 1)
								{
									if (branch[index - 1].inning)
									{
										index--;
										goto cut02;
									}
								}
								else//如果已经截到最后一个分支
									if (branch[0].inning)
									{
										win = true;//最后一个分支是黑的,黑必胜
										break;
									}
								if (select[index - 1] < z[index - 1].n)//这个白分支
									cache = *tap(&branch[index - 1], z[index - 1].pd[select[index - 1]++]);//从这个白回合的其它分支继续下棋检查
								else
									if (index - 1)//所有分支是否还没检查完毕
									{
										index--;//丢弃当前用完的分支继续检查
										goto cut02;
									}
									else
									{
										win = true;//检查到有无论白怎么走都输的情况,黑可以必胜
										break;//已经得出最终结论,终止计算
									}
							}
							else//如果没有分支,则黑必胜
							{
								win = true;
								break;
							}
						}
					}
					else
					{
						branch[index] = cache, z[index] = h, select[index++] = 1;
						cache = *tap(&cache, h.pd[0]);
						goto g2;
					}
				else//说明黑输了,这是黑的回合预判,检查黑还有没有必胜的机会
				{
					if (index > 0)
					{
					cut12:
						if (index - 1)
						{
							if (!branch[index - 1].inning)
							{
								index--;
								goto cut12;
							}
						}
						else//如果已经截到最后一个分支
							if (!branch[0].inning)
							{
								win = false;//最后一个分支是白的,白必胜
								break;
							}
						if (select[index - 1] < z[index - 1].n)//这个黑分支
						{
							cache = *tap(&branch[index - 1], z[index - 1].pd[select[index - 1]++]);//从这个黑回合的其它分支继续下棋检查
							goto g2;
						}
						else
							if (index - 1)//所有分支是否还没检查完毕
							{
								index--;//丢弃当前用完的分支继续检查
								goto cut12;
							}
							else
							{
								win = false;//检查到无论黑怎么走都输,黑无必胜方法
								break;//已经得出最终结论,终止计算
							}
					}
					else//如果没有分支,则黑必输
					{
						win = false;
						break;
					}
				}
			}
		}
		else
			root = *tap(&root, play[index2++]);
		root = *tap(&root, play[index2++]);
		if (win)//上局黑胜,记白错
			round_of_error[num_of_error++] = index2 / 2;
		if (index2 >= rounds)
			break;
	}
	//验证成果
	cout << num_of_error;
	for (i = 0; i < num_of_error; i++)
		cout << endl << round_of_error[i];
	return 0;
}
2025/1/5 16:20
加载中...