美文网首页
Codeforces 1360E - Polygon

Codeforces 1360E - Polygon

作者: 费城的二鹏 | 来源:发表于2020-06-01 21:34 被阅读0次

猫咪短暂的和谐时光,之后的场景就是俩猫打架了。

翻译

Polygon 不只是一个最好的开发问题平台,而是一个边长为 n 的正方形,初始填充字符 0。

在这个正方形上进行训练,士兵在每行每列放置一大炮,放置方式如图:

大炮将会射击字符 1,同时只有一门大炮射击。当字符 1 飞出大炮后,直到碰到右边或者下面的边框,或者碰到字符 1 才会停下来。

你的桌上有很多训练结束的图表。你在考虑,这些训练结果是不是真实的。

输入格式

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

每个测试用例起始输入一个整数 n,标识正方形的边长。

接下来 n 行,每行输入 n 个字符,0 或 1。

可以保证所有 n 的平方的和不大于 10^5。

输出格式

如果训练表可能是真实的,输出 YES,否则输出 NO。

分析

因为炮在左边和上边,所以无论什么情况都可以上边和左边交替开炮,来组成结果。

这道题可以用动态规划的方式解决,默认最下边和最右边的一定能完成,然后从倒数第二行开始遍历,接下来是倒数第二列,倒数第三行,倒数第三列 。。。

动态规划的公式就是,判断每个点的下方或者右方是否是 1,如果都不是 1,那么就是假的表格。

总结起来就是很简单的动态规划。

代码(PyPy3)

# https://codeforces.com/problemset/problem/1360/E

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

for _ in range(t):
    n = int(input())
    m = []
    for _ in range(n):
        arr = input()
        m.append(arr)

    result = 'YES'
    for row in range(n - 2, -1, -1):
        # line
        for col in range(row - 1, -1, -1):
            if m[row][col] == '1':
                if m[row + 1][col] != '1' and m[row][col + 1] != '1':
                    result = 'NO'
        
        # col
        for col in range(row, -1, -1):
            if m[col][row] == '1':
                if m[col + 1][row] != '1' and m[col][row + 1] != '1':
                    result = 'NO'
        
    print(result)

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

by 费城的二鹏 2020.05.25 长春

相关文章

网友评论

      本文标题:Codeforces 1360E - Polygon

      本文链接:https://www.haomeiwen.com/subject/syyyahtx.html