← 返回题目列表

Codeforces · 844/B

B. 矩形

中文机器翻译题面 查看原题

给你 n × m 表。表中的每个单元格颜色为白色或黑色。求非空单元格的数量,使得:

1. 集合中的所有单元格具有相同的颜色。
2. 集合中的每两个单元格共享行或列。

输入

输入的第一行包含整数 n 和 m (1 ≤ n, m ≤ 50) — 相应的行数和列数。

接下来的 n 行输入包含行的描述。每行有 m 个整数,用空格分隔。如果相应的单元格为白色,则该数字等于 0;如果相应的单元格为黑色,则该数字等于 1。

输出

输出单个整数 - 问题描述中非空集的数量。

示例

输入 #1

1 1
0

输出 #1

1

输入 #2

2 3
1 0 1
0 1 0

输出 #2

8

注意

在第二个示例中,有六个单元素集。此外,还有两个双元素集,第一个由第一行的第一个和第三个单元格组成,第二个由第二行的第一个和第三个单元格组成。总结起来就是8套。