填充NxM矩阵，使得A [i，j] = A [i-1，j] NAND A [i，j-1] [关闭]

Question

输入：

i）长度为N的字符串，由1和0组成

ii）长度为M的串，由1和0组成

iii）空格分隔的整数对i，j的列表

输出：

每个i，j的[i，j]作为输入给出。

A [i，j] = A [i-1，j] NAND A [i，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]))

Answer 1

我建议查看一些示例序列产生的模式，例如：

    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 

我没有仔细分析它，但乍一看似乎一旦你模拟了前几行和列，那么模式的其余部分只是一个对角线扩展。