填充NxM矩阵，使得A[i，j]=A[i-1，j] NAND A[i，j-1]
填充NxM矩阵，使得A[i，j]=A[i-1，j] NAND A[i，j-1]
提问于 2018-09-15 20:19:34
输入：
一条长度为N的字符串，由1s和0组成
( ii)长度M的串，由1s和0组成。
(Iii)空格分隔整数对i，j的列表
输出：
i，j对于输入的每一个i，j。
Ai，j=Ai-1，j NAND Ai，j-1.
第一行作为第一个字符串，第一列作为第二个字符串(右上角的元素为空)。
我已经通过遍历矩阵中的每个元素的蛮力方法来解决问题，我正在试图想出优化我的代码的方法。我想让它运行得足够快，以便N=10^5和M=10^5在2-3秒内运行。
r=[]
N=list(map(int,list(input())))
M=list(map(int,list(input())))
n=len(N)
m=len(M)
Y=[1 for j in range(m+1)]
A=[Y.copy() for i in range(n+1)]
A[0]=[-1]+M
for i in zip(A[1:],N):
i[0][0]=i[1]
for k in range(1,min(n,m)+1):
for i in range(k,n+1):
if (A[i-1][k] and A[i][k-1]):
A[i][k]=0
for j in range(k+1,m+1):
if (A[k-1][j] and A[k][j-1]):
A[k][j]=0
q=int(input())
for i in range(q):
qj,qi=map(int,input().split())
r.append(str(A[qi][qj]))回答 1
Stack Overflow用户
回答已采纳
发布于 2018-09-15 21:56:02
我建议看看一些示例序列产生的模式，例如：
X XXXX X X XX X X XXXXXXXX
XXXX X X XXXX X X XX X X X X X X
X XX X X X XX X X XX X X X X X
X X XX X X X XX X X XX X X X X X
XX X XX X X X XX X X XX X X X X
X X X XX X X X XX X X XX X X X X
XX X X XX X X X XX X X XX X X X
XX X X XX X X X XX X X XX X X X
X XX X X XX X X X XX X X XX X X
X XX X X XX X X X XX X X XX X X
X X XX X X XX X X X XX X X XX X
X X XX X X XX X X X XX X X XX X
XX X XX X X XX X X X XX X X XX
X X X XX X X XX X X X XX X X XX
XX X X XX X X XX X X X XX X X X
X XX X X XX X X XX X X X XX X X
X XX X X XX X X XX X X X XX X X
XX XX X X XX X X XX X X X XX X
X X XX X X XX X X XX X X X XX X
XX X XX X X XX X X XX X X X XX
X X X XX X X XX X X XX X X X XX
XX X X XX X X XX X X XX X X X X
X XX X X XX X X XX X X XX X X X
XX XX X X XX X X XX X X XX X X X
X X XX X X XX X X XX X X XX X X
X X XX X X XX X X XX X X XX X X
X X X XX X X XX X X XX X X XX X
X X X XX X X XX X X XX X X XX X
X X X X XX X X XX X X XX X X XX
XX X X X XX X X XX X X XX X X XX
XX X X X XX X X XX X X XX X X X
X XX X X X XX X X XX X X XX X X 我还没有仔细分析过它，但乍一看，似乎一旦您模拟了前几行和列，那么模式的其余部分就只是一个对角线扩展。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52348527
复制相关文章
相似问题
腾讯云开发者
