QOJ.ac

QOJ

実行時間制限: 1.0 s メモリ制限: 1024 MB 満点: 100 ハック可能 ✓

#9695. 垃圾问题

統計

给定一个 $n \times n$ 的网格,其中每个单元格要么是黑色(0),要么是白色(1)。

计算满足以下条件的矩形区域的数量:区域内的所有白色单元格都可以被若干个互不重叠的 $2 \times 2$ 正方形完全覆盖,且没有任何黑色单元格被覆盖。每个 $2 \times 2$ 正方形必须完全位于该区域内,且由四个白色单元格组成。

输入格式

第一行包含一个正整数 $n$,表示网格的大小($1 \le n \le 300$)。

接下来的 $n$ 行,每行包含一个长度为 $n$ 的字符串,由数字 ‘0’ 和 ‘1’ 组成。这些行表示网格的各行。

输出格式

输出一个整数:满足条件的矩形区域的数量。

样例

输入 1

4
0110
0110
1111
1111

输出 1

17

说明

请注意,不包含任何白色单元格的区域也被视为有效的区域。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.