Editorial for 第3回卬高杯 F問題 - 増殖する鶴の剣
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
概説
紀元\(1\)年に鶴の剣信仰が存在しない地域.に斜めを含めて\(T\)回で隣接する座標には紀元前\(T\)年に鶴の剣が襲来していないことがわかる。
そうでなければ\(T\)年後の紀元\(1\)年にその地域には鶴の剣信仰が存在することになってしまうからだ。
紀元前\(T\)年に鶴の剣が襲来していないとわかる地域以外は鶴の剣が襲来したと考えても問題ないため、鶴の剣が襲来したとする。
これにより、紀元前\(T\)年の鶴の剣襲来地域の候補を作成できるため、その\(T\)年後と入力を比較し、同じであればその地域数を、でなければ-1を出力すればよい。
imos法やDFS,BFSなどで実装することが可能であり、\(O(HW)\)と十分高速である。
Python
Python3 imos法を用いた
h,w,t=map(int,input().split())
s=[[0]*(w+1) for i in range(h+1)]
s2=[[0]*(w+1) for i in range(h+1)]
imo=[[0]*(w+1) for i in range(h+1)]
imo2=[[0]*(w+1) for i in range(h+1)]
for i in range(h):
si=input()
for j in range(w):
if si[j]=="#":s[i][j]=1
for i in range(h):
for j in range(w):
if not s[i][j]:
imo[max(0,i-t)][max(0,j-t)]+=1
imo[max(0,i-t)][min(w,j+t+1)]-=1
imo[min(h,i+t+1)][max(0,j-t)]-=1
imo[min(h,i+t+1)][min(w,j+t+1)]+=1
for i in range(h+1):
for j in range(w):
imo[i][j+1]+=imo[i][j]
for i in range(h):
for j in range(w+1):
imo[i+1][j]+=imo[i][j]
for i in range(h):
for j in range(w):
s2[i][j]=(imo[i][j]==0)and s[i][j]
for i in range(h):
for j in range(w):
if s2[i][j]:
imo2[max(0,i-t)][max(0,j-t)]+=1
imo2[max(0,i-t)][min(w,j+t+1)]-=1
imo2[min(h,i+t+1)][max(0,j-t)]-=1
imo2[min(h,i+t+1)][min(w,j+t+1)]+=1
for i in range(h+1):
for j in range(w):
imo2[i][j+1]+=imo2[i][j]
for i in range(h):
for j in range(w+1):
imo2[i+1][j]+=imo2[i][j]
ans=0
for i in range(h):ans+=sum(s2[i])
for i in range(h):
for j in range(w):
if (imo2[i][j]==0)!=(s[i][j]==0):ans=-1
print(ans)
Comments