글 읽기 - 질문 드리겠습니다.

tkfkddlfk7 4년 전 0

우선 예제로 제시된 코드는 다 잘나옵니다.

전체 Map에서 치킨 집와 집 위치를 싹 벡터에 모으고

집과 치킨집간의 거리를 계산하면서 최저 값인 경우를 찾아 단계를 넘어가는

그리디 식으로 구현하고자 하였습니다.

어떤부분이 문제일지 지적해주시면 감사하겠습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<memory.h>
#include<stdlib.h>
#include<numeric>

using namespace std;

int N,M,K;

int map[51][51] = { 0, };
bool visit[14] ={false,};

vector< pair<int,int> > v1; // house
vector< pair<int,int> > v2; //chicken

int minmin=222222;

int calcul(vector< pair<int,int> > temp_v){
		int accum=0;
		for(int idx=0;idx<v1.size();idx++){
			int mm=1234567;
			for(int i=0;i<temp_v.size();i++){
				mm = min(mm,abs(v1[idx].first-temp_v[i].first)+abs(v1[idx].second-temp_v[i].second));
			}
			accum+=mm;
		}
		return accum;
}

void solve(int index,int bound,vector<pair<int,int>> temp_v){
	if(index == bound){

		minmin = min(minmin,calcul(temp_v));
		
		return;
	}

	for(int i=0;i<v2.size();i++){
		if(!visit[i]){
			if(temp_v.size()==0){
					visit[i]=true;
					temp_v.push_back(v2[i]);
					solve(index+1,bound,temp_v);
					temp_v.pop_back();
					visit[i]=false;
			}
			else{
				visit[i]=true;
				temp_v.push_back(v2[i]);
				if(minmin>calcul(temp_v)){
					solve(index+1,bound,temp_v);
				}			
				temp_v.pop_back();
				visit[i]=false;
			
			}

			
		}
	}


}



int main() {

	   
	scanf(" %d %d", &N, &M);
	int aa;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			scanf(" %d",&aa);
			if(aa==1) v1.push_back(make_pair(i,j));
			if(aa==2){
				v2.push_back(make_pair(i,j));
			}
		}
	}
	
	for(int i=1;i<=M;i++){
		vector<pair<int,int>> vv;
		solve(0,i,vv);	
	}
	printf("%d",minmin);
	
	
    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

질문 드리겠습니다.

tkfkddlfk7 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말