結果

問題 No.3504 Insert Maze
コンテスト
ユーザー Ryan Shaw
提出日時 2026-04-17 22:20:14
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 231 ms / 2,000 ms
コード長 2,721 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,858 ms
コンパイル使用メモリ 271,716 KB
実行使用メモリ 132,736 KB
最終ジャッジ日時 2026-04-17 22:20:28
合計ジャッジ時間 13,680 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'void initcatalan(long long int)':
main.cpp:85:59: warning: iteration 1000002 invokes undefined behavior [-Waggressive-loop-optimizations]
   85 |         for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
      |                                                   ~~~~~~~~^
main.cpp:85:24: note: within this loop
   85 |         for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
      |                       ~^~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cstdio>
#include <stdio.h>
#include <stdbool.h>
#include <iostream>
#include <map>
#include <vector>
#include <climits>
#include <stack>
#include <string>
#include <queue>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <cctype>
#include <bitset>
#include <iomanip>
#include <cstring>
#include <numeric>
#include <cassert>
#include <random>
#include <chrono>
#include <fstream> 
using namespace std;

#define int long long
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back

const int MOD = 998244353;//
const int FACTMAX = 2000005;//
const int CATALANMAX = 1000005;//

int fact[FACTMAX], invfact[FACTMAX], cat[CATALANMAX];

int expo(int a, int b){
	int res=1;
	a%=MOD;
	while (b){
		if (b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}

int inv(int num){
	return expo(num, MOD-2);
}

void initfact(){
	fact[0]=1;
	for (int i=1; i<FACTMAX; ++i)fact[i]=(fact[i-1]*i)%MOD;
	invfact[FACTMAX-1]=inv(fact[FACTMAX-1]);
	for (int i=FACTMAX-2; i>=0; --i)invfact[i]=(invfact[i+1]*(i+1))%MOD;
}
 
int ncr(int n, int r){
	if (n<r||r<0)return 0;
	return (((fact[n]*invfact[r])%MOD)*invfact[n-r])%MOD;
}

int gcd(int a, int b){
	while (b){
		int t=a%b;
		a=b;
		b=t;
	}
	return a;
}

int lcm(int a, int b){
	int temp=gcd(a, b);
	a/=temp;
	b/=temp;
	return a*b*temp;
}

void initcatalan(int k){
	cat[0]=1;
	for (int i=1; i<CATALANMAX; ++i)cat[i]=(((fact[2*i]*invfact[i])%MOD)*invfact[i+1])%MOD;
}

int h, w, rh, rw;
vector<string> grid;

bool inside(int r, int c){
	return 0<=r&&r<rh&&0<=c&&c<rw;
}

bool usable(int r, int c){
	if (!inside(r, c))return 0;
	if (r%2==0&&c%2==0)return grid[r/2][c/2]!='#';
	return 1;
}

int32_t main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin>>t;
	while (t--){
		cin>>h>>w;
		grid.resize(h);
		for (int i=0; i<h; ++i)cin>>grid[i];
		rh=2*h-1;
		rw=2*w-1;
		vector<vector<int> > dp(rh, vector<int>(rw, LLONG_MAX/2));
		dp[0][0]=0;
		for (int r=0; r<rh; ++r){
			for (int c=0; c<rw; ++c){
				if (!usable(r, c)) continue;
				if (dp[r][c]==LLONG_MAX/2) continue;
				int cur=dp[r][c];
				if (c%2==0){
					if (c+1<rw&&usable(r, c+1))dp[r][c+1]=min(dp[r][c+1], cur+1);
					if (c+2<rw&&usable(r, c+2))dp[r][c+2]=min(dp[r][c+2], cur+1);
				}
				else if (c+1<rw&&usable(r, c+1))dp[r][c+1]=min(dp[r][c+1], cur+1);
				if (r%2==0){
					if (r+1<rh&&usable(r+1, c))dp[r+1][c]=min(dp[r+1][c], cur+1);
					if (r+2<rh&&usable(r+2, c))dp[r+2][c]=min(dp[r+2][c], cur+1);
				}
				else if (r+1<rh&&usable(r+1, c))dp[r+1][c]=min(dp[r+1][c], cur+1);
			}
		}
		if (dp[rh-1][rw-1]==LLONG_MAX/2)cout<<"-1";
		else cout<<dp[rh-1][rw-1];
	}
}
0