Submission #3782184


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;
  unordered_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

Submission Time
Task S - マス目
User chocorusk
Language C++14 (GCC 5.4.1)
Score 7
Code Size 2572 Byte
Status AC
Exec Time 576 ms
Memory 256 KB

Judge Result

Set Name All
Score / Max Score 7 / 7
Status
AC × 8
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 90, 91
Case Name Status Exec Time Memory
00 AC 559 ms 256 KB
01 AC 576 ms 256 KB
02 AC 30 ms 256 KB
03 AC 12 ms 256 KB
04 AC 2 ms 256 KB
05 AC 2 ms 256 KB
90 AC 1 ms 256 KB
91 AC 8 ms 256 KB