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


翻译
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 长春
网友评论