← 返回题单
题单练习 挑战赛 普及/提高- 题
← 上一题 下一题 →

A4802 | 梦神的大平层

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

*Yuilice*最近一直在失眠，一夜未眠都是非常正常的事情，所以他去向梦神求助，希望能够通过梦神的帮助解决这个问题。

梦神给了Yuilice一个难题，让他每天睡觉前去解题从而每天都睡得香香的，但是*坏心眼的的楠楠*因为晚上打CS找不到开黑的伙伴，所以他决定解开这个难题从而让Yuilice再次失眠，彻夜在米垃圾被折磨。

现在为了保护Yuilice的好梦，你需要抢在楠楠之前解开这道谜题，打开题目之后，你惊讶的发现问题居然是梦神的大平层设计图。

现在已知梦神的大平层可以由一个$N \times M$的二维矩阵来表示，同时在矩阵的每一个格子当中，都会有一个数字$a_{i,j}(1 \leq a_{i,j} \leq 15)$，代表在该格当中哪个方向有着墙壁(每个格子都有自身的四面墙壁)。

例如数字5，可以被视为是二进制的0101:
  • 第一个数字0代表北面没有墙壁
  • 第二个数字1代表东面有墙壁
  • 第三个数字0代表南面没有墙壁
  • 第四格数字1代表西面有墙壁。
现在已知在大平层当中，每个房间会被墙壁所包围起来(但是房间内可能存在墙壁而不是刚好包围)，请你求出每个房间所占的方格总数，并且按照从大到小的顺序进行输出每个房间的所占方格总数。

输入格式

第一行共会输入两个整数$N,M(1 \leq N,M \leq 10^3)$，代表大平层的二维矩阵。

随后$N$行，每行输入$M$个整数$a_{i,j}$，代表每个方格的状态。

输出格式

按照从大到小的顺序输出每个房间的所占方格总数，每两个数字之间用空格隔开。

输入输出样例

输入 #1
4 5
9 14 11 12 13
5 15 11 6 7
5 9 14 9 14
3 2 14 3 14
输出 #1
9 4 4 2 1
输入 #2
3 3
9 8 12 
5 5 5
7 7 7
输出 #2
9
输入 #3
3 3
9 8 13
15 7 15
15 15 6
输出 #3
3 1 1 1 1 1 1
C++ 编辑器
输入
输出