Submission #59206810

---

Source Code Expand

#include <bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
#define cmp(a) sort(all(a));a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
typedef modint1000000007 mi;
constexpr ll mod=1000000007;

unordered_map<int,ll>dp[578];

int main(){
	int h,w;cin>>h>>w;
	string c[24];
	rep(i,h)cin>>c[i];
	dp[0][0]=1;

	if(w==1){
		vector<ll>dp2(h+2);
		dp2[0]=1;
		rep(i,h){
			dp2[i+1]+=dp2[i];
			if(c[i][0]=='.')dp2[i+2]+=dp2[i];
		}
		cout<<dp2[h]+dp2[h+1]<<endl;
		return 0;
	}

	rep(i,h){
		rep(j,w){
			int d=i*w+j;
			for(auto e:dp[d]){
				int k=e.first;
				dp[d+1][k>>1]+=e.second;
				dp[d+1][k>>1]%=mod;
				if(c[i][j]=='.'&&!(k&1)){
					if(j==w-1){
						dp[d+1][(k>>1)|(3<<(w-2))]+=e.second;
						dp[d+1][(k>>1)|(3<<(w-2))]%=mod;
					}
					else if(j==0){
						dp[d+2][(k>>2)|(3<<(w-2))]+=e.second;
						dp[d+2][(k>>2)|(3<<(w-2))]%=mod;
					}
					else{
						dp[d+2][(k>>2)|(7<<(w-3))]+=e.second;
						dp[d+2][(k>>2)|(7<<(w-3))]%=mod;
					}
				}
			}
		}
	}

	ll res=0;
	for(int i=h*w;i<=h*w+1;i++){
		for(auto e:dp[i])res=(res+e.second)%mod;
	}
	cout<<res<<endl;
}

Submission Info

Judge Result