結果

問題 No.3504 Insert Maze
コンテスト
ユーザー sig_256
提出日時 2026-04-18 22:49:39
言語 C++17(gcc12)
(gcc 12.4.0 + boost 1.89.0)
コンパイル:
g++-12 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 148 ms / 2,000 ms
コード長 1,568 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,215 ms
コンパイル使用メモリ 78,216 KB
実行使用メモリ 7,552 KB
最終ジャッジ日時 2026-04-18 22:50:06
合計ジャッジ時間 13,190 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>

int main() {
	int H, W, maxH = 0, maxW = 0;
	std::cin >> H >> W;
	std::vector<std::vector<char>> C(H, std::vector<char>(W));
	for (auto& l : C) for (char& c : l) std::cin >> c;
	C.back().back() = '.';
	for (int w = 1; w < W; ++w) {
		if (C.front()[w - 1] == 'S' && C.front()[w] == '.') {
			if (w > maxW) maxW = w;
			C.front()[w] = 'S';
		}
	}
	for (int h = 1; h < H; ++h) {
		if (C[h - 1].front() == 'S' && C[h].front() == '.') {
			if (h > maxH) maxH = h;
			C[h].front() = 'S';
		}
		for (int w = 1; w < W; ++w) {
			if ((C[h][w - 1] == 'S' || C[h - 1][w] == 'S') && C[h][w] == '.') {
				if (w > maxW) maxW = w;
				if (h > maxH) maxH = h;
				C[h][w] = 'S';
			}
		}
	}
	if (C.back().back() == 'S') {
		std::cout << H + W - 2 << '\n';
		return 0;
	}
	maxH += 2;
	maxW += 2;
	if (W <= maxW || H <= maxH) {
		std::cout << H + W - 1 << '\n';
		return 0;
	}
	C.back().back() = 'G';
	for (int w = W - 1; w-- > 0;) {
		if (C.back()[w + 1] == 'G' && C.back()[w] == '.') {
			if (w < maxW) {
				std::cout << H + W - 1 << '\n';
				return 0;
			}
			C.back()[w] = 'G';
		}
	}
	for (int h = H - 1; h-- > 0;) {
		if (C[h + 1].back() == 'G' && C[h].back() == '.') {
			if (h < maxH) {
				std::cout << H + W - 1 << '\n';
				return 0;
			}
			C[h].back() = 'G';
		}
		for (int w = W - 1; w-- > 0;) {
			if ((C[h][w + 1] == 'G' || C[h + 1][w] == 'G') && C[h][w] == '.') {
				if (h < maxH || w < maxW) {
					std::cout << H + W - 1 << '\n';
					return 0;
				}
				C[h][w] = 'G';
			}
		}
	}
	std::cout << H + W << '\n';
	return 0;
}
0