UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#2513. 菜园

Statistics 下载数据

Description

       你有一个N*M大的长方形菜园,每个格子代表一块田地。 现在你想要检查一下菜园内的田地,于是你决定从右上角出发,在菜园里走一圈回到右上角。最后,所有在你走过的这个环内的田地都被认为检查过了。为了保护植物,你的路径只能在田地边界的小路上走,不能走到田地里面。并且你走过的路径不能自交, 小路保证足够宽,你可以多次沿着一条小路走,并且这些路径都不相交。
       先在给你菜园的地图,其中有的田地标记为”I”,表示这些田地是你想要检查的;有的田地被标记为”X”,表示这些田地是你不想检查的;有的田地被标记为”.”,表示这些田地你不关心。
       假设菜园中有K个”I”,那么你要输出K个数字,其中第i个数为:恰好检查任意i个标记为”I”的田地,并且没有检查任何一个标记为”X”的田地的最短路。

Input

        输入的第一行为NM表示田地大小。
       接下来N行,每行M个字母(”I” ,”X” 或 ”.”)描述菜园。

Output

       输出一行,K个数字用空格隔开,如题目描述中所述。

Sample Input

2 2
XX
XI

Sample Output

8


Hint

       30%满足K=1;

       100%数据满足N,M≤50,除了”.”之外的字符最多10个。

Source

2010福建集训