# 散场电影 – 题解

agc044_b

## 分析

For each $$1 \leq i \leq N^2$$ , we compute the minimum number of viewers that will hate viewer $$i$$ forever (the answer is the sum of these values). This number coincides with the minimum cost of a path from the seat of viewer $$i$$ to the sides of the square, considering that going through an empty seat has cost 0 and going through an occupied seat has cost 1. Let $$H_k(i)$$ be the minimum cost (as defined above) of a path from the seat of viewer i to the outside after the first $$k$$ viewers have left the cinema.

Key observation
The values $$H_k(i)$$ are decreasing (for $$k$$ going from $$0$$ to $$N^2$$ ) and at the beginning we have
$\sum_{k=1}^{N^2}{H_0(k)} \approx \frac{N^3}{6}$

Our strategy is to keep all values $$H_k(i)$$ updated at all times. Initializing $$H_0(1), … , H_0(N^2 )$$ in $$O(N^2)$$ is straightforward. Let us show how to update $$H_{k−1}(1), … , H_{k−1}(N^2 )$$ to get $$H_k(1), … , H_k(N^2 )$$. When the viewer $$P_k$$ goes away, we perform a breadth-first search (or a depth-first search) starting from the seats of $$P_k$$ and updating the values. During the k-th breadth-first search, we will visit only the seats $$i$$ such that $$H_k(i) < H_{k−1}(i)$$, hence the total number of seats visited in the $$N^2$$ steps (for $$1 \leq k \leq N^2 )$$ is $$O(N^3 )$$ (see the key observation).

The time complexity of this solution is $$O(N^3 )$$ with a small constant which is sufficient to get accepted (some optimization might be required in slow languages such as python).