Submission #3782179

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;
int par[21];
int rk[21];
void init(int n){
	for(int i=0; i<n; i++){
		par[i]=i;
      rk[i]=0;
	}
}
int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}
void unite(int x, int y){
	x=find(x);
	y=find(y);
	if(x==y) return;
	if(rk[x]<rk[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(rk[x]==rk[y]) rk[x]++;
	}
}
bool same(int x, int y){
	return find(x)==find(y);
}
int main()
{
	int h, w;
  cin>>h>>w;
  map<string, ll> dp[2];
  for(int i=1; i<(1<<h); i+=2){
    init(h);
    for(int j=1; j<h; j++){
      if((i&(1<<(j-1))) && (i&(1<<j))){
        unite(j-1, j);
      }
    }
    int p[6], c=1; fill(p, p+h, -1);
    string s;
    for(int j=0; j<h; j++){
      if(i&(1<<j)){
        if(p[find(j)]==-1){
          p[find(j)]=c;
          c++;
        }
        s+=('0'+p[find(j)]);
      }else{
        s+='0';
      }
    }
    dp[0][s]=1;
  }
  for(int l=1; l<w; l++){
    for(int i=1; i<(1<<h); i++){
      for(auto p:dp[(l-1)&1]){
        string t=p.first;
        init(3*h);
        for(int k=0; k<h; k++){
          if(t[k]>'0'){
            unite(t[k]-'0', k+h);
            if(i&(1<<k)){
              unite(k+h, k+2*h);
            }
          }
        }
        for(int k=1; k<h; k++){
          if(t[k]>'0' && t[k-1]>'0'){
            unite(k-1+h, k+h);
          }
          if((i&(1<<(k-1))) && (i&(1<<k))){
            unite(k-1+2*h, k+2*h);
          }
        }
        int q[18]; fill(q, q+3*h, -1);
        int c=2;
        q[find(1)]=1;
        string s; bool ok=0;
        for(int k=0; k<h; k++){
          if(i&(1<<k)){
            if(q[find(k+2*h)]==-1){
              q[find(k+2*h)]=c;
              c++;
            }else if(q[find(k+2*h)]==1){
              ok=1;
            }
            s+=('0'+q[find(k+2*h)]);
          }else{
            s+='0';
          }
        }
        if(!ok) continue;
        dp[l&1][s]+=p.second;
        dp[l&1][s]%=MOD;
      }
    }
    dp[(l-1)&1].clear();
  }
  ll ans=0;
  for(auto p:dp[(w-1)&1]){
    string t=p.first;
    if(t[h-1]=='1'){
      ans=(ans+p.second)%MOD;
    }
  }
  cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result