COI '16 #2 Raspad

View as PDF

Submit solution

All submissions

Best submissions

Points: 30 (partial)

Time limit: 6.0s

Memory limit: 1G

Problem type

A nearby meadow consists of quadratic fields organized in $n$ $n$ rows and $m$ $m$ columns. The rows are denoted with numbers from $1$ $1$ to $n$ $n$ from top to bottom, and the columns with numbers from $1$ $1$ to $m$ $m$ from left to right. Some fields are grass fields (denoted with 1), whereas some are underwater because of the heavy spring rainfall (denoted with 0). Two grass fields are connected if it is possible to get from one field to another using a series of moves where, in each step, we move to the adjacent grass field located up, down, left or right. A component is a set of mutually connected grass fields that is maximal in the sense that, if $A$ $A$ is a field in the component $K$ $K$ , then all the adjacent grass fields of $A$ $A$ are also in the component $K$ $K$ .

For a given meadow $P$ $P$ and indices $a$ $a$ and $b$ $b$ $(1 \le a \le b \le n)$ $(1 \leq a \leq b \leq n)$ , $P^a_b$ $P_{b}^{a}$ is a meadow consisting of rows between the $a^\text{th}$ $a^{th}$ and the $b^\text{th}$ $b^{th}$ row of the original meadow $P$ $P$ (including both $a^\text{th}$ $a^{th}$ and $b^\text{th}$ $b^{th}$ row). The complexity of meadow $P^a_b$ $P_{b}^{a}$ is the number of components of the grass fields located on the meadow. Determine the sum of the complexities of all possible meadows $P^a_b$ $P_{b}^{a}$ .

Input Specification

The first line of input contains the positive integers $n$ $n$ and $m$ $m$ — dimensions of the meadow. Each of the following $n$ $n$ lines contains a string of exactly $m$ $m$ characters that denotes one row of the meadow. Each character of the string is either the digit 0 or the digit 1.

Output Specification

You must output the required sum of all complexities.

Constraints

Subtask	Score	Constraints
$1$ $1$	$9$ $9$	$n \le 100, m \le 50$ $n \leq 100, m \leq 50$
$2$ $2$	$17$ $17$	$n \le 1\,000, m \le 50$ $n \leq 1 000, m \leq 50$
$3$ $3$	$35$ $35$	$n \le 100\,000, m \le 15$ $n \leq 100 000, m \leq 15$
$4$ $4$	$39$ $39$	$n \le 100\,000, m \le 50$ $n \leq 100 000, m \leq 50$

Sample Input 1

Copy

Sample Output 1

Copy

Explanation for Sample Output 1

If we denote the complexity of meadow $P^a_b$ $P_{b}^{a}$ with $|P^a_b|$ $| P_{b}^{a} |$ then it holds that $|P^1_1| = 2, |P^1_2| = 1, |P^1_3| = 1, |P^1_4| = 1, |P^2_2| = 1, |P^2_3| = 1, |P^2_4| = 1, |P^3_3| = 2, |P^3_4| = 2, |P^4_4| = 2$ $| P_{1}^{1} | = 2, | P_{2}^{1} | = 1, | P_{3}^{1} | = 1, | P_{4}^{1} | = 1, | P_{2}^{2} | = 1, | P_{3}^{2} | = 1, | P_{4}^{2} | = 1, | P_{3}^{3} | = 2, | P_{4}^{3} | = 2, | P_{4}^{4} | = 2$ , and the sum of these numbers is $14$ $14$ .

Sample Input 2

Copy

Sample Output 2

Copy

Sample Input 3

Copy

4 12
011111010111
110000101001
110111101111
111101111111

Sample Output 3

Copy

Comments

There are no comments at the moment.