UOJ Logo

NOI.AC

#85. water

统计

水池灌水

时间限制:1秒,内存限制:128MB

读入文件名:water.in

输出文件名:water.out

【题目描述】

有一个$n*m$的网格水池,其中有$k$个水源,依次在坐标为$(x_1,y_1)$,$\ldots$,$(x_k,y_k)$的网格里。

在第0秒时,整个水池是干涸的;在第1秒时,每个水源所在的格子被灌入了水;随后所有灌了水的格子都会在下一秒漫到上下左右相邻的干涸的格子里,直到将整个水池灌满。

问在第几秒时,整个水池会被灌满水,并输出过程中每一秒水池中有多少格是有水的。

【输入格式】

输入有$k+1$行,第一行为三个正整数$n$、$m$、$k$,表示水池的大小和水源个数,用一个空格隔开。

接下来$k$行每行2个正整数$x_i$和$y_i$,表示对应水源的坐标,用一个空格隔开,$1\le x_i\le n$,$1\le y_i\le m$。

【输出格式】

输出共两行,第一行一个整数$t$,表示灌满水池所需要的时间。 第二行$t$个整数,表示从第1秒到第$t$秒,每一秒时水池中有水的格子总数,输出间用一个空格分隔。

【输入输出样例1】

water.in

4 5 2
2 3
3 4

water.out

5
2 8 15 19 20

【输入输出样例2】

water.in

5 5 1
3 3

water.out

5
1 5 13 21 25

【数据规模与约定】

对于前20%的数据,$1\le n,m\le 10$,$k=1$;

对于前50%的数据,$1\le n,m\le 100$,$1\le k\le 10$;

对于100%的数据,$1\le n,m\le 1000$,$1\le k\le 100$;

【样例1解释】

'x'代表干涸,'o'代表有水

t=0
xxxxx
xxxxx
xxxxx
xxxxx

t=1
xxxxx
xxoxx
xxxox
xxxxx

t=2
xxoxx
xooox
xxooo
xxxox

t=3
xooox
ooooo
xoooo
xxooo

t=4
ooooo
ooooo
ooooo
xoooo

t=5
ooooo
ooooo
ooooo
ooooo