题解 CF1365A 【Matrix Game】

更佳的阅读效果

description:

  • 给定一个 $n\times m$ 的矩阵,有一些格子是 $1$,有一些格子是 $0$。

  • Ashish 和 Vivek 轮流往矩阵中放 $1$。某个格子可以放 $1$ 当且仅当这个格子所在的行和列没有 $1$。

  • 最后无处放 $1$ 的玩家就输了。你需要输出赢家的姓名。

  • 多组数据,数据组数不超过 $50$, $1\le n,m\le 50$。

  • translate by @ShineEternal

solution:

这道题目 $n,m$ 的范围较小,所以直接模拟即可。

由于先后顺序并没有影响,故按顺序添加就好。

在添加 $1$ 的时候记录下当前是谁走的。可以使用 TUrn=(TUrn+1)%2; 类似的标记器。


update soon:

突然发现其实取出空行和空列的最小值判断奇偶性就行了。

code:

#include<cstdio>
#include<cstring>
using namespace std;
int a[55][55];
int x[55],y[55];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(x,0,sizeof(x));
        memset(y,0,sizeof(y));
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                if(a[i][j]==1)
                {
                    x[i]=1;
                    y[j]=1;
                }
            }
        }
        int TUrn=1;
        for(int i=1;i<=n;i++)
        {
            if(x[i]==0)
            {
                int flag=0;
                //x[i]=1;
                for(int j=1;j<=m;j++)
                {
                    if(y[j]==0)
                    {
                        y[j]=1;
                        flag=1;
                        break;
                    }
                }
                if(flag==1)
                {
                    x[i]=1;
                    TUrn=(TUrn+1)%2;
                }
            }
        }
        if(TUrn==1)
        {
            printf("Vivek\n");
        }
        else
        {
            printf("Ashish\n");
        }
    }
    return 0;
} 

发表于 2020-06-08 19:16:48 in 题解