結果

問題 No.3679 なんかでっかい虫リターンズ
コンテスト
ユーザー doqusa (どくーさ)
提出日時 2026-09-06 00:21:34
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 2 ms / 2,000 ms
+ 321µs
コード長 2,317 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,513 ms
コンパイル使用メモリ 235,820 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2026-09-06 00:21:44
合計ジャッジ時間 3,936 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>
#include <iostream>//cin/cout
#include <string>//cout string
#include <functional>//rambda
#include <algorithm>
#include <iterator>//next/prev
#include <cmath>
#include <numeric>//iota
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <stack>
//#include <atcoder/modint.hpp>
//using namespace atcoder;

using namespace std;

using llong = long long;
const llong INF = 1LL << 60;//INF > 10^18(1e18)
const int INF32 = 1LL << 30;//INF32 > 10^9(1e9)

template <typename T> bool chmax(T& max, const T& b) {
	if (max >= b) return false;
	max = b;	return true;
}
template <typename T> bool chmin(T& min, const T& b) {
	if (min <= b) return false;
	min = b;	return true;
}

///////////////////ここまでtoolbox/////////////////////////////////////

int main() {
	int H, W;
	cin >> H >> W;
	int A, B;
	cin >> A >> B;
	A--; B--;
	int R1, C1, R2, C2;
	cin >> R1 >> C1 >> R2 >> C2;
	R1--; C1--; R2--; C2--;
	int P, Q;
	cin >> P >> Q;
	P--; Q--;
	//動画がないとわからんかったが、虫のどのマスなら岩井星人の距離＋ごみ箱の距離が最短になるか総当たり
	vector<vector<int>>len1(H, vector<int>(W, INF32)), len2(H, vector<int>(W, INF32));
	struct QUE {
		int h, w, step;
	};
	queue<QUE>q;
	q.push({ A,B,0 });
	len1[A][B] = 0;
	while (!q.empty()) {
		auto[h,w,step] = q.front();
		q.pop();
		int dh[] = { 0,0,-1,1 };
		int dw[] = { -1,1,0,0 };
		for (int dir = 0; dir < 4; dir++) {
			int nh = h + dh[dir];
			int nw = w + dw[dir];
			if (nh < 0 or H <= nh or nw < 0 or W <= nw) {
				continue;
			}
			if (len1[nh][nw] <= step + 1) { continue; }
			len1[nh][nw] = step + 1;
			q.push({ nh,nw,step + 1 });
		}
	}
	q.push({ P,Q,0 });
	len2[P][Q] = 0;
	while (!q.empty()) {
		auto [h, w, step] = q.front();
		q.pop();
		int dh[] = { 0,0,-1,1 };
		int dw[] = { -1,1,0,0 };
		for (int dir = 0; dir < 4; dir++) {
			int nh = h + dh[dir];
			int nw = w + dw[dir];
			if (nh < 0 or H <= nh or nw < 0 or W <= nw) {
				continue;
			}
			if (len2[nh][nw] <= step + 1) { continue; }
			len2[nh][nw] = step + 1;
			q.push({ nh,nw,step + 1 });
		}
	}
	int step = INF32;
	for (int h = R1; h <= R2; h++) {
		for (int w = C1; w <= C2; w++) {
			chmin(step,len1[h][w] + len2[h][w]);
		}
	}
	step += len1[P][Q];
	cout << step << endl;
	return 0;
}
0