Codeforces 1360E - Polygon

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

翻译

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 长春