結果

問題 No.611 Day of the Mountain
ユーザー WA_TLEWA_TLE
提出日時 2017-12-11 01:48:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 350 ms / 2,017 ms
コード長 3,385 bytes
コンパイル時間 1,582 ms
コンパイル使用メモリ 136,448 KB
最終ジャッジ日時 2025-01-05 05:08:06
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
const int mod=201712111;
const llint big=1e15+100;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
template <class T> void soun(T& ar)
{sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
int main(void){
	int i,j,h,w,bi;cin>>h>>w;
	vector<string>kyuri(h);//山なので
	for(i=0;i<h;i++){cin>>kyuri[i];}
	if(h<w){
		vector<string>ne(w);//ぬえっ!
		for(i=0;i<w;i++){ne[i].res(h);}
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				ne[j][i]=kyuri[i][j];
			}
		}
		swap(h,w);
		swap(kyuri,ne);
	}
	//w>hになったw<=18
	//bitDPPPPPPPPP
	vector<vector<int>>time(h);
	for(i=0;i<h;i++){
		time[i].res(w);
		for(j=0;j<w;j++){
			if(i==0&&j==0){time[i][j]=0;}//(0ではない)
			else if(i==0){time[i][j]=time[i][j-1];}
			else if(j==0){time[i][j]=time[i-1][j];}
			else{time[i][j]=min(time[i][j-1],time[i-1][j]);}
			if(kyuri[i][j]=='?'){time[i][j]++;}
			else{time[i][j]+=kyuri[i][j]-'0';}
		}
	}
	
	int T=time[h-1][w-1];
	cout<<T<<endl;
	vector<vector<int>>Rtime(h);
	for(i=h-1;i>=0;i--){
		Rtime[i].res(w);
		for(j=w-1;j>=0;j--){
			if(i==h-1&&j==w-1){Rtime[i][j]=0;}
			else if(i==h-1){Rtime[i][j]=Rtime[i][j+1];}
			else if(j==w-1){Rtime[i][j]=Rtime[i+1][j];}
			else{Rtime[i][j]=min(Rtime[i][j+1],Rtime[i+1][j]);}
			if(kyuri[i][j]=='?'){Rtime[i][j]++;}
			else{Rtime[i][j]+=kyuri[i][j]-'0';}
		}
	}
	vector<vector<int>>just(h);
	for(i=0;i<h;i++){
		just[i].res(w);
		for(j=0;j<w;j++){
			int kor;
			if(kyuri[i][j]=='?'){kor=1;}
			else{kor=kyuri[i][j]-'0';}
			if(Rtime[i][j]+time[i][j]==T+kor){just[i][j]=1;}
			else{just[i][j]=0;}
		}
	}
	vector<llint>bdp(1<<w);
	bdp[1]=1;
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(i==0&&j==0){continue;}
			vector<llint>ndp(1<<w);
			int bji=(1<<j);
			int kor;if(kyuri[i][j]=='?'){kor=1;}else{kor=kyuri[i][j]-'0';}
			bool uecan=(i!=0&&time[i-1][j]+kor==time[i][j]&&just[i][j]==1);
			bool yocan=(j!=0&&time[i][j-1]+kor==time[i][j]&&just[i][j]==1);
			
			for(bi=0;bi<(1<<w);bi++){
				bool uearu=uecan&&((bi&bji)!=0);
				bool yoaru=yocan&&((bi&(bji/2))!=0);
				if(uearu||yoaru){ndp[bi|bji]+=bdp[bi];}
				else{ndp[bi-(bi&bji)]+=bdp[bi];}
				if(kyuri[i][j]=='?'){ndp[bi-(bi&bji)]+=bdp[bi]*8;}
			}
			for(bi=0;bi<(1<<w);bi++){ndp[bi]%=mod;}
			bdp=move(ndp);
		}
	}
	llint ans=0;
	for(bi=(1<<(w-1));bi<(1<<w);bi++){ans+=bdp[bi];ans%=mod;}
	cout<<ans<<endl;
	return 0;
}
0