最近AtCoderでよく見る、「実装の重いB問題」でしたね。
問題概要
- 9x9マスの領域で、左上と右下の3x3マスがそれぞれ黒('#')、その周りを囲う部分が白('.')になっているものをTaK Codeと呼ぶ。
縦Nマス、横Mマスのグリッドがある。そこに含まれる9x9マスの領域のうち、「TaK Code」の部分の左上の座標を全て出力せよ。
下図がTaK Code('#'が黒、'.'が白、'?'はどちらでも良い)
###.????? ###.????? ###.????? ....????? ????????? ?????.... ?????.### ?????.### ?????.###
解説
親切にもTaK Codeが出ているので、これをコピー&ペーストして調べたい部分と比較する。
比較の方法については、調べたい9x9マスの左上のマスを引数として受け取る関数を作り、9x9の範囲全てをTaK Codeと比べていく。実際は '?' である部分まで見る必要はないが、細かい範囲を考えるよりはすべて見たほうが楽。もし '?' でない部分で異なるならその場でFalseを返し、最後まで間違いがなかったらTrueを返すようにする。
あとは二重for文でfor i in range(N): for j in range(M):if (判定関数(i,j)…のようにしていき、結果がTrueなら(i,j)を出力すると、自然と辞書順になり条件を満たす。
なお、右下の一部のマスではそもそも(i,j)を左上にして正方形を作ることができないが、関数側でもし範囲をオーバーしそうになったらFalseを返す実装にすると、条件を満たさないi・jの範囲を考える手間を省ける。
実装
実装では、左上のマスを(0, 0)として考える。
#TaK Codeはコピペして、少し改造してリストにする tak = ["###.?????", "###.?????", "###.?????", "....?????", "?????????", "?????....", "?????.###", "?????.###", "?????.###"] # Sの(i, j)を左上とする9x9がTaKであるかを判定する関数 def takcheck(i, j): global N, M # N, Mが関数内でも使えるようにする # Sの調べている部分の座標(i+a, j+b)とTaKの(a, b)を比較 for a in range(9): for b in range(9): #もしi+aまたはj+bが範囲外(9x9が作れない)ならばFalseを返す if not (0 <= i+a < N and 0 <= j+b < M): return False # もしTaKが?なら調べない if tak[a][b] == "?": continue # もし異なるならFalseを返す if S[i+a][j+b] != tak[a][b]: return False # もし最後まで異なるものがなければTrueを返す return True N,M = map(int, input().split()) S = [input() for _ in range(N)] # (i, j)全ての組において for i in range(N): for j in range(M): # もしtakcheck(i,j)がTrueなら if takcheck(i,j): # 実際は左上は(1,1)であるため1を足して出力 print(i+1, j+1)
