# USACO 2020 January Contest, Platinum Problem 1. Cave Paintings

### USACO 2020 January Contest, Platinum Problem 1. Cave Paintings

Bessie has become an artist and is creating paintings of caves! Her current work in progress is a grid of height NN such that each row of the grid contains exactly MM squares (1N,M10001≤N,M≤1000). Each square is either empty, filled with rock, or filled with water. Bessie has already painted the squares containing rock, including the entire border of the painting. She now wants to fill some empty squares with water such that if the painting were real, there would be no net motion of water. Define the height of a square in the ii-th row from the top to be N+1iN+1−i. Bessie wants her painting to satisfy the following constraint:

Suppose that square aa is filled with water. Then if there exists a path from aa to square bb using only empty or water squares that are not higher than aa such that every two adjacent squares on the path share a side, then bb is also filled with water.

Find the number of different paintings Bessie can make modulo 109+7109+7. Bessie may fill any number of empty squares with water, including none or all.

#### SCORING:

• Test cases 1-5 satisfy N,M10.N,M≤10.
• Test cases 6-15 satisfy no additional constraints.

#### INPUT FORMAT (file cave.in):

The first line contains two space-separated integers NN and MM.The next NN lines of input each contain MM characters. Each character is either '.' or '#', representing an empty square and a square filled with rock, respectively. The first and last row and first and last column only contain '#'.

#### OUTPUT FORMAT (file cave.out):

A single integer: the number of paintings satisfying the constraint modulo 109+7109+7.

#### SAMPLE INPUT:

4 9
#########
#...#...#
#.#...#.#
#########


#### SAMPLE OUTPUT:

9


If a square in the second row is filled with water, then all empty squares must be filled with water. Otherwise, assume that no such squares are filled with water. Then Bessie can choose to fill any subset of the three horizontally contiguous regions of empty squares in the third row. Thus, the number of paintings is equal to 1+23=9.1+23=9.

Problem credits: Daniel Zhang

<h3> USACO 2020 January Contest, Platinum Problem 1. Cave Paintings 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Daniel Zhang, Benjamin Qi)

Define a relation RR on empty and water cells where aRbaRb if and only if aa being water implies that bb is water. It is clearly reflexive and transitive. Also note that if aRbaRb then height(a)height(b)height(a)≥height(b). Thus, cycles can only exist between vertices on the same layer. However, if we restrict the relation to cells with the same height, it is also symmetric. Thus, we can divide cells on each layer into (completely connected) equivalence classes.

Compressing these equivalence classes, we get a directed acyclic graph (DAG). Note that equivalence classes are not edge-connected; for example, in the sample case, the squares on the second row are all in the same equivalence class. Let GG be the graph with the minimum number of edges whose transitive closure is the DAG. (To compute the transitive closure of a graph, if edges aba→b and bcb→c exist then add edge aca→c, if it is not already present in the graph.)

If there is an edge from aa to bb in the DAG, then height(a)=height(b)+1height(a)=height(b)+1. Suppose otherwise. Clearly height(a)>height(b)height(a)>height(b). There must be a path from aa to bb using only cells of height at most height(a)height(a). Take the last vertex cc on that path with height height(b)+1height(b)+1 (it must exist). This divides the path into a path from aa to cc using cells of height at most height(a)height(a) and a path from cc to bb using cells of height at most height(c)height(c). This contradicts the minimality of GG.

Each node has at most one predecessor. Suppose there is an edge from aa to bb and an edge from cc to bb. Then, height(a)=height(b)+1=height(c)height(a)=height(b)+1=height(c) and concatenating the paths yields a path from aa to cc using only cells of height at most height(a)height(a). Then aa and cc must be the same equivalence class.

Hence, GG is a (directed) forest. GG can be computed efficiently from the cave by sweeping upwards with a union-find data structure. Then, this problem can be solved by DP on GG.

Ben - I didn't have any solution in mind for the N,M10N,M≤10 subtask. It was merely intended to be a small correctness test.

#include <cstdio>
#include <cstring>
#include <vector>

const int MOD=1e9+7;

char grid[1005][1005];

int uf[1005][1005];
int up[1005][1005];
int id[1005][1005];

std::vector<int> children[1005*1005];
int tree_size=1;

int dp[1005*1005];

int find(int layer,int a){
while(uf[layer][a]!=a){
a=uf[layer][a]=uf[layer][uf[layer][a]];
}
return a;
}

void merge(int layer,int a,int b){
a=find(layer,a),b=find(layer,b);
uf[layer][a]=b;
}

void pull(int i){
dp[i]=1;
//product of children if not filling root
for(int j:children[i]){
dp[i]=1LL*dp[i]*dp[j]%MOD;
}
//+1 for filling root (and everything else)
dp[i]++;
}

int main(){
freopen("cave.in","r",stdin);
freopen("cave.out","w",stdout);
int N,M;
scanf("%d %d",&N,&M);
for(int i=0;i<N;i++){
scanf("%s",grid[i]);
}
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
uf[i][j]=j;
}
}
memset(up,-1,sizeof up);
for(int i=N-1;i>=0;i--){
for(int j=0;j<M;j++){
uf[i][j]=j;
}

for(int j=0;j+1<M;j++){
if(grid[i][j]=='.'&&grid[i][j+1]=='.'){
merge(i,j,j+1);
}
}
if(i<N-1){
for(int j=0;j<M;j++){
if(grid[i][j]=='.'&&grid[i+1][j]=='.'){
if(up[i+1][find(i+1,j)]==-1){
up[i+1][find(i+1,j)]=j;
}else{
merge(i,j,up[i+1][find(i+1,j)]);
}
}
}
}
}
for(int i=N-1;i>=0;i--){
for(int j=0;j<M;j++){
if(grid[i][j]=='.'&&find(i,j)==j){
id[i][j]=tree_size++;
}
}
}
for(int i=N-1;i>=0;i--){
for(int j=0;j<M;j++){
if(grid[i][j]=='.'&&find(i,j)==j){
if(up[i][j]!=-1){
children[id[i-1][find(i-1,up[i][j])]].push_back(id[i][j]);
}else{
children[0].push_back(id[i][j]);
}
}
}
}
for(int i=1;i<tree_size;i++){
pull(i);
}
pull(0);
printf("%d\n",(dp[0]+MOD-1)%MOD);
}