#1157956 (C++23) No.3504 Insert Maze

• 問題: No.3504 Insert Maze
• ユーザー: askr58
• 提出日時: 2026-04-17 21:28:27
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 144 ms / 2,000 ms
• コード長: 1,045 bytes
• コンパイル時間: 3,015 ms
• コンパイル使用メモリ: 341,824 KB
• 実行使用メモリ: 12,544 KB
• 最終ジャッジ日時: 2026-04-17 21:28:55
• 合計ジャッジ時間: 12,389 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 85

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
	int h,w;
	cin>>h>>w;
	vector<string> s(h);
	for(int i=0;i<h;i++)cin>>s[i];
	vector<vector<bool>> a(h,vector<bool>(w)),b(h,vector<bool>(w));
	a[0][0]=true;
	b[h-1][w-1]=true;
	for(int i=0;i<h;i++)for(int j=0;j<w;j++){
		if(a[i][j]){
			if(i<h-1&&s[i+1][j]!='#')a[i+1][j]=true;
			if(j<w-1&&s[i][j+1]!='#')a[i][j+1]=true;
		}
	}
	for(int i=h-1;i>=0;i--)for(int j=w-1;j>=0;j--){
		if(b[i][j]){
			if(i>0&&s[i-1][j]!='#')b[i-1][j]=true;
			if(j>0&&s[i][j-1]!='#')b[i][j-1]=true;
		}
	}
	if(a[h-1][w-1]){
		cout<<h+w-2<<endl;
		return 0;
	}
	vector<int> ca(h,w),ra(w,h),cb(h,-1),rb(w,-1);
	for(int i=0;i<h;i++)for(int j=0;j<w;j++){
		if(a[i][j]){
			ca[i]=min(ca[i],j);
			ra[j]=min(ra[j],i);
		}
		if(b[i][j]){
			cb[i]=max(cb[i],j);
			rb[j]=max(rb[j],i);
		}
	}
	for(int i=0;i<h-1;i++){
		if(ca[i]<=cb[i+1]){
			cout<<h+w-1<<endl;
			return 0;
		}
	}
	for(int j=0;j<w-1;j++){
		if(ra[j]<=rb[j+1]){
			cout<<h+w-1<<endl;
			return 0;
		}
	}
	cout<<h+w<<endl;
}