Preparing NOJ
There is a large grid of size $$$n \times m$$$, where each grid cell is either colored or uncolored.
To make some artwork on the grid, Hyunuk wants to put some sheets of colored paper in some of the uncolored cells. Hyunuk selects two integers $$$w, h$$$ where $$$1 \le w \le m, 1 \le h \le n$$$. Then, Hyunuk covers the grid with sheets of colored paper of width $$$w$$$ and height $$$h$$$, satisfying the following conditions.
Depending on the selection of width and height, Hyunuk may fail to cover the grid satisfying the above conditions. Please compute the number of possible sheet sizes that can cover the grid satisfying all the above conditions.
The first line contains two integers $$$n$$$ and $$$m \, (1 \le n, m \le 3\,000)$$$.
The next $$$n$$$ lines each contain a length $$$m$$$ string denoting the state of the grid. . denotes an uncolored cell, and # denotes a colored cell.
There is at least one uncolored cell in the grid.
Output the number of possible sheet sizes that can cover the grid satisfying all the above conditions.
3 3 ..# ... #..
4
8 9 ......... ......... ......... ...#..... .....#... ....#.... ......... .........
4
9 9 ######... ######... ######... #........ #.....### #.....### #####.... #####.... #####....
9
5 5 ..... ....# ...## ..### .####
1
In the first example, the following four colored paper satisfy the conditions: $$$1 \times 1$$$, $$$1 \times 2$$$, $$$2 \times 1$$$, and $$$2 \times 2$$$. Since the colored paper can not be rotated, $$$1 \times 2$$$ and $$$2 \times 1$$$ are considered different sizes.
Info
Provider CodeForces Gym
Origin XXII Open Cup. Grand Prix of Korea
Code GYM103371I
Tags
Submitted 0
Passed 0
AC Rate 0%
Date 10/31/2021 14:45:19
Related