質問リンク:https://www.acmicpc.net/problem/9205

質問する

松島に住んでいる尚根さんと友達は松島で行われるPentaPortRock祭りに行きます.今年はビールを飲みながら歩くことにしました.出発は尚勤家で、ビールを一箱持って出発.1箱のビールには20個のビールがある.喉が渇いていないので、50メートルごとに1本飲むつもりです.
尚根の家で祭りをするところは遠いです.そのため、もっとビールを買う必要があるかもしれません.事前にネットで調べていたら、幸いビールを売っているコンビニがありました.コンビニに入る時、空き瓶を捨てて新しいビール瓶を買うことができます.しかし、箱の中のビールは20本を超えてはいけません.
コンビニ、上根家、ペンシルベニア港ロックフェスティバルの座標です.サンゲンと友達が幸せに祭りに着くかどうか、番組を作ってみましょう.

入力

第1行は、試験例の個数tを与える.(t ≤ 50)
各テストボックスの最初の行には、ビールを売っているコンビニの数nが与えられています.(0 ≤ n ≤ 100).
次のn+2行は、上根家、コンビニ、PentaPortrock Festival座標を与えます.各座標は2つの整数xとyからなる.(両方ともm,−32768≦x,y≦32767)
松島は長方形の町です.2つの座標間の距離は、x座標の差+y座標の差である.(マンハッタン通り)

しゅつりょく

各テストボックスについて、尚根と友人たちが幸せに祭りに行けば「happy」、真ん中のビールが切れたら「sad」と出力されます.

に答える

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

int visited[102] = { 0, };
std::vector<int> g[102];

void dfs(int start) {
	visited[start] = true;

	for (int i = 0; i < g[start].size(); i++) {
		int next = g[start][i];

		if (!visited[next]) {
			dfs(next);
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cout.tie(NULL);
	std::cin.tie(NULL);

	int t; std::cin >> t;

	for (int tc = 0; tc < t; tc++) {
		for (int i = 0; i < 102; i++) {
			g[i].clear();
		}

		memset(visited, 0, sizeof(visited));

		int n; std::cin >> n;
		std::vector<std::pair<int, int>> v(n + 2);

		for (int i = 0; i < n + 2; i++) {
			std::cin >> v[i].first >> v[i].second;
		}
		
		for (int i = 0; i < n + 2; i++) {
			for (int j = i + 1; j < n + 2; j++) {
				if (abs(v[i].first - v[j].first) + abs(v[i].second - v[j].second) <= 1000) {
					g[i].push_back(j);
					g[j].push_back(i);
				}
			}
		}

		dfs(0);

		if (visited[n + 1]) {
			std::cout << "happy\n";
		}
		else {
			std::cout << "sad\n";
		}
	}

	return 0;
}

深度優先ナビゲーション(DFS)、幅優先ナビゲーション(BFS)
資料構造の授業でグラフを勉強して探索法を学ぶのは、個人的に難しいアルゴリズムだと思います.
これは簡単なdfs問題で,グラフを作成し,アクセスしたことのない場所で探索しhappyやsadを出力すればよい.

ノート

これからは,できるだけdfs,bfsを主として問題を解決する.
これはPS問題を解決する基礎であり、困難や面倒も避けられない.