[解決済み] 行または列に 0 が含まれる場合、行列のすべてのセルに 0 を設定します。

質問

0と1を持つNxN行列が与えられる。を含むすべての行を設定します。 0 をすべて 0 を含むすべてのカラムを設定し 0 をすべて 0 s.

例えば

1 0 1 1 0
0 1 1 1 0
1 1 1 1 1
1 0 1 1 1
1 1 1 1 1

の結果

0 0 0 0 0
0 0 0 0 0
0 0 1 1 0
0 0 0 0 0
0 0 1 1 0

マイクロソフトのエンジニアから、余分なメモリを使わず、2つのブーリアン変数と1つのパスだけで解決する方法があると聞いたので、その答えを探しています。

ちなみに、ビット行列なので、行列に入れることができるのは1と0だけだと想像してください。

どのように解決するのですか？

私は午前3時なので疲れていますが、私はインプレースで行列の各数値にちょうど2パスで最初のトライを持っているので、O（NxN）で、それは行列のサイズに線形である。

1列目と1行目を目印にして、1しかない行や列がどこにあるのか分かるようにしています。そして、1行目/1列目がすべて1であるかどうかを記憶するために、2つの変数lとcがあります。 つまり、最初のパスではマーカーを設定し、残りを0にリセットします。

2回目のパスでは、行と列が1であるとマークされた場所に1をセットし、lとcに応じて1行目/列をリセットします。

最初のマス目が最後のマス目に依存するので、1パスでできるのかどうか、強く疑問です。2パス目はもっと効率的にできるかもしれませんが...。

import pprint

m = [[1, 0, 1, 1, 0],
     [0, 1, 1, 1, 0],
     [1, 1, 1, 1, 1],
     [1, 0, 1, 1, 1],
     [1, 1, 1, 1, 1]]



N = len(m)

### pass 1

# 1 rst line/column
c = 1
for i in range(N):
    c &= m[i][0]

l = 1
for i in range(1,N):
    l &= m[0][i]


# other line/cols
# use line1, col1 to keep only those with 1
for i in range(1,N):
    for j in range(1,N):
        if m[i][j] == 0:
            m[0][j] = 0
            m[i][0] = 0
        else:
            m[i][j] = 0

### pass 2

# if line1 and col1 are ones: it is 1
for i in range(1,N):
    for j in range(1,N):
        if m[i][0] & m[0][j]:
            m[i][j] = 1

# 1rst row and col: reset if 0
if l == 0:
    for i in range(N):
        m [i][0] = 0

if c == 0:
    for j in range(1,N):
        m [0][j] = 0


pprint.pprint(m)