[ZJOI2009]染色游戏

NC20487. [ZJOI2009]染色游戏

描述

一共n × m 个硬币，摆成n × m 的长方形。dongdong 和xixi 玩一个游戏，每次可以选择一个连通块，并把其中的硬币全部翻转，但是需要满足存在一个硬币属于这个连通块并且所有其他硬币都在它的左上方(可以正左方也可以正上方)，并且这个硬币是从反面向上翻成正面向上。

dongdong和xixi轮流操作。如果某一方无法操作，那么他(她) 就输了。dongdong 先进行第一步操作，假设双方都采用最优策略。问dongdong 是否有必胜策略。

输入描述

第一行一个数T，表示他们一共玩T局游戏。
接下来是T组游戏描述。每组游戏第一行两个数n,m，
接下来n 行每行m 个字符，第i行第j个字符如果是“H” 表示第i行第j列的硬币是正面向上，否则是反面向上。第i行j列的左上方是指行不超过i 并且列不超过j的区域。

输出描述

对于每局游戏，输出一行。如果dongdong 存在必胜策略则输出“-_-”(不含 引号) 否则输出“=_=”(不含引号)。(注意输出的都是半角符号，即三个符号 ASCII 码分别为45,61,95)

示例1

输入:

3
2 3
HHH
HHH
2 3
HHH
TTH
2 1
T
H

输出:

=_=
-_-
-_-

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 6ms, 内存消耗: 376K, 提交时间: 2021-02-14 14:17:35

#include<bits/stdc++.h>
using namespace std;
bool vis[220];
inline int lowbit(int x)
{
	return x&(-x);
 } 
inline int sg(int i,int j)
{
	if(i&&j)
	return i+j;
	else
	return log2(lowbit(i+j+1));
}
char s[110][110];
int main()
{
	int T,n,m;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		memset(vis,0,sizeof(vis));
		for(int i=0;i<n;i++)
		{
			scanf("%s",s[i]);
			for(int j=0;j<m;j++)
			{
				if(s[i][j]=='T')
				{
					vis[sg(i,j)]^=1;
				}
			}
		}
		int flag=0;
		for(int i=0;i<n+m-1;i++)
		{
			if(vis[i])
			{
				printf("-_-\n");
				flag=1;
				break;
			}
		}
		if(!flag)
		printf("=_=\n");
	}
	return 0;
}

上一题

下一题

详情