题目描述
~~关于 WDCCR1 太水而惨被淘汰这件事~~
一群奶牛正在 Farmer John 的农场里吃草,但由于它们昨晚在牛圈里开派对时吃了太多的神秘食物,导致现在所有奶牛都想喷射。
奶牛们都是懂文明讲礼貌的,因此它们每头牛都想找到最近的茅房。已知农场可以表示为一张 $n\times m$ 的网格图,每间茅房能够同时容纳无限只奶牛,每头奶牛每秒钟可以向四周(上、下、左、右)任意一个方向跑一格,同一位置在同一时刻也可以容纳无限只奶牛,但它们不能跑到稻草堆的位置上。
紧急调度这件事可难坏了 Farmer John,毕竟这可是个脑力活。因此请你帮帮他,问如果每一头奶牛都往离自己最近的茅房跑去,至少需要多少秒才能让所有奶牛都到达茅房?当然,可能有些奶牛被困在了稻草堆圈内无法动弹,因此也请你求出有多少只奶牛只能被迫就地解决吧。
输入格式
第一行包含两个正整数 $n,m$,分别表示农场的长与宽。
其后 $n$ 行,每行 $m$ 个字符,表示农场,其中字符 $W$ 表示一个茅房,字符 $C$ 表示一头奶牛,字符 $.$ 表示一个空地(可以经过),字符 $\#$ 表示稻草堆(不可以经过)。
数据保证农场内至少有一头牛,且至少有一间茅房,但茅房的总数量不会超过 $100$ 间。
- $4 \le n,m \le 1000$
输出格式
输出两个整数,以空格隔开,分别表示**让所有奶牛都到达离自己最近的茅房所需要的最少秒数**及**就地解决的奶牛数量**。
如果所有奶牛都无法到达任何一个茅房,秒数输出 $-1$。
样例输入 #1
4 5
W#C..
.....
C####
.#C#W