[C/C++]白俊(BOJ)15686チキン出前

3243 ワード
白駿 フルナビゲーション C テキストリンク

質問の概要📌




質問リンク📢


https://www.acmicpc.net/problem/15686

問題を解く📝


入力してみると、都市部に存在するチキン屋の最大数は13店.また,Nは最大50であるため,NxNアレイも大きなアレイではないので,完全なナビゲーションで解決できる.
まず、存在するすべての家とフライドチキン店の座標をベクトルに格納します.そしてM個のフライドチキン屋を選び、選ぶ際に順番は関係ないので、組み合わせを使って選んだ後、組み合わせのために別々に作ったベクトルに保存します.
そしてベクトルに格納された情報に基づいて,各店から選りすぐりのチキン屋までの最小距離を求める.組み合わせの数を繰り返し、最小値を更新することで、都会のチキンストリートを手に入れることができます!

コード#コード#

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
#include<cmath>

#define INF 1e9;
using namespace std;
typedef pair<int, int> pii;
vector<pii> v, cPos,hPos;
int visited[55][55];
int map[55][55];
int N, M, minDist, sum, minSum = INF;
void go()
{
	if (v.size() == M) // M개의 조합을 선정한 뒤
	{
		sum = 0;
		for (int i = 0; i < hPos.size(); i++)
		{
			minDist = INF;			
			for (int j = 0; j < v.size(); j++) 
			{
				int dist = abs(hPos[i].first - v[j].first) + abs(hPos[i].second - v[j].second);
				minDist = min(minDist, dist);//치킨거리를 구한다
			}
			sum += minDist;
		}
		minSum = min(minSum, sum); // 최소 도시의 치킨거리를 갱신!
	}
	for (int i = 0; i < cPos.size(); i++)
	{
       // 가능한 모든 경우를 탐색하기 위해 좌표를 조합을 사용하여 확인한다!
		if (!v.empty() && v.back() >= cPos[i]) continue;
		if (visited[cPos[i].first][cPos[i].second] == 0)
		{
			visited[cPos[i].first][cPos[i].second] = 1;
			v.push_back(cPos[i]);
			go();
			visited[cPos[i].first][cPos[i].second] = 0;
			v.pop_back();
		}
	}
}
int main()
{
	cin >> N >> M;
	
	for (int i = 1; i < N + 1; i++)
	{
		for (int j = 1; j < N + 1; j++)
		{
			cin >> map[i][j];
			if (map[i][j] == 1) hPos.push_back({ i,j });
			if (map[i][j] == 2) cPos.push_back({ i,j });
		}
	}
	
	go();
	cout << minSum;
	return 0;
}
div同業者実装またはdiv自動改行
［アルゴリズム］DFSとBFS