ABC430 B – Count Subgrid

B - Count Subgrid

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

n行n列のグリッドからm行m列のグリッドを取り出して得られるマスの塗られ方が何種類あるかを求める問題。

m行m列のグリッドを覚えておかないとと思って色々考えていたら、setで持てば良いのではと閃いて何とか解けました。

m行m列を1次元のtupleで持ち、setの変数に追加していく。

setは重複を許さないのでsetの要素数がそのまま答えになる。

以下でACできました。

def i_map(): return map(int, input().split())
def i_list(): return list(map(int, input().split()))

n, m = i_map()
s = [list(input()) for _ in range(n)]
tmp = set()
ans = 0

for i in range(n-m+1):
  for j in range(n-m+1):
    g = []
    for y in range(m):
      for x in range(m):
        g.append(s[i+y][j+x])
    tmp.add(tuple(g))

print(len(tmp))Code language: PHP (php)