Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
O(|bishops| + n) diagonal sweep solution in Speedy category for Dangerous Bishops by StefanPochmann
def safe_squares(n, bishops):
D = [1] * (2*n - 1)
E = D[:]
for i, j in bishops:
D[i+j] = E[i-j] = 0
safe = 0
e = e_other = 0
for k in range(n):
d = D[k] + D[~k] * (k < n-1)
e, e_other = e_other, e
e += E[k] + E[-k] * (k > 0)
safe += d * e
return safe
May 22, 2024
Comments: