Codeforces 1365A - Matrix Game

日常一道算法题。

翻译

Ashish 和 Vivek 在一个 n 行 m 列的矩阵上玩一个游戏，轮流认领格子。未被认领的格子用 0 表示，被认领的格子用 1 表示。初始的矩阵已经被提供了，并且可能初始有被认领的格子。

每个轮次，一个玩家必须标记一个格子。一个格子只有在它所在行和列都没有被认领的格子的情况下，才能被认领。当一个玩家不能认领格子的时候就输了。

如果两个人玩这个游戏，并且 Ashish 先手，确认赢得游戏的人是谁，如果两个人都用最优的行动方案。

输入格式

输入整数 t 表示测试用例组数。

每个测试用例第一行输入 n m 用空格分隔。

接下来输入 n 行数字，每行 m 个用空格分隔。

输出格式

每行输出 Ashish 或者 Vivek。

分析

统计有多少空行和多少空列，然后计算两个数值最小的那个，表示两个人可以操作的轮次数。

轮次为奇数则 Ashish 获胜，轮次为偶数则 Vivek 获胜。

代码(Python3)

# https://codeforces.com/problemset/problem/1365/A
 
import sys
import os
import heapq
import math
 
try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass
 
t = int(input())
 
def printd(value):
    # print(value)
    pass
 
def case():
    arr = list(map(int, input().split(" ")))
    n, m = arr[0], arr[1]

    matrix = []
    for row in range(n):
        rows = list(map(int, input().split(" ")))
        matrix.append(rows)
    
    empty_row_count = 0
    for row in range(n):
        count = 1
        for col in range(m):
            if matrix[row][col] == 1:
                count = 0
        empty_row_count += count
    
    empty_col_count = 0
    for col in range(m):
        count = 1
        for row in range(n):
            if matrix[row][col] == 1:
                count = 0
        empty_col_count += count
    
    print("Ashish" if min(empty_row_count, empty_col_count) % 2 == 1 else "Vivek")

for _ in range(t):
    case()

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.06.12 长春