AtCoder Beginner Contest 173 C問題

C問題

難易度：茶色

一発クリアです！

H行W列のマスに対して、
h行目もしくはw列目のマスを選択し、赤に塗りつぶす。

最終的に黒色のマスとして残った合計がKである選択する行・列のパターンを出力します。

解き方はHとWが6以下であるため、総当たりでいけるか
と思い、総当たり探索で解きました。

まず行と列の数を数え、
考えうる選択行・選択列の組み合わせをitertoolsで列挙します。

1行目だけ
1行目と1列目
1行目と1列目と2列目
・・・といった風に。
そしてこの選択行列の組み合わせパターンを配列にまとめます。

黒色：#、白色：・と定義していましたが
黒色：1、白or赤色：0に変換。
数値に変換した方が後々楽なので、Numpy配列に変換。

二次元配列をスライスして、
各行・列を選択し、赤(0)に塗りつぶします。

最終的に黒色(1)の数を知りたいので、
配列全体の合計値がそのまま黒色のマスの合計になりました！

import numpy as np
import itertools
H,W,K = map(int,input().split())
all_,choice = [],[]

lis = ['h'+str(h) for h in range(H)]
w_lis = ['w'+str(w) for w in range(W)]
lis.extend(w_lis)

for j in range(0,len(lis)+1):
  choice.extend(list(itertools.combinations(lis,j)))

for h in range(H):
  l = list(input().replace('#','1').replace('.','0'))
  all_.append(l)

all_ = np.array(all_,dtype=int)
ans = 0

for i in choice:
  A = all_.copy()
  for k in i:
    if k==None:
      pass
    elif k[0]=='h':
      A[int(k[1]),:]=0
    elif k[0]=='w':
      A[:,int(k[1])]=0
  #print(A)
  if A.sum()==int(K):
    ans+=1
      
print(ans)