글 읽기 - 치킨 배달 문제 반례가 뭐가 있을까요?

smc3534 4년 전 0

치킨 배달 문제를 풀고 예시 조건에는 알맞는 답이 나오는데, 어디서 답이 잘 못 도출 되는지 모르겠습니다.

한 번 봐주시면 감사하겠습니다.

#include<cstdio>
#include<utility>
#include<stdlib.h>

using namespace std;

int n,m,n_chic,n_house,limit;
int min = 100000,s_min;
int map[50][50];
pair< int,int > a_chic[30];
pair< int,int > a_house[30];
int s_chic[30];

void calc()
{
	int t_dis = 0,s_dis =10000000;
	int dis;
	
	for(int i = 0; i < n_house; i++)
	{
		for(int j =0;j < m; j++)
		{
			dis = abs(a_chic[s_chic[j]].first - a_house[i].first) +abs(a_chic[s_chic[j]].second - a_house[i].second);
	//		printf("house y : %d x : %d chic y : %d x : %d  dis : %d\n",a_house[i].first,a_house[i].second,a_chic[s_chic[j]].first,a_chic[s_chic[j]].second,dis);
			if(s_dis > dis)s_dis = dis;
		}
		t_dis+=s_dis;
		s_dis = 100000000;
	}
//	printf("tdis : %d\n",t_dis);
	if(min > t_dis)
	{
		min = t_dis;
	}
	
}

void dfs(int idx,int cnt) /// idx는 전체 치킨집에서의 idx이고 cnt는 선택된 치킨집 갯 스 
{
	/// idx 전체치킨 리스트에서 순서 
	if(cnt>m-1)
	{
		calc();
		return;
	}
	
	if(idx>n_chic-1)return; 
	
	if(s_chic[cnt]!=-1)s_chic[cnt] = idx;
	
	dfs(idx+1,cnt+1);
	s_chic[cnt] = -1;
	dfs(idx+1,cnt);
}

void solve()
{

		dfs(0,0);	

}

void init()
{
	freopen("chic.txt","r",stdin);
	setbuf(stdout,NULL);
	scanf("%d %d",&n,&m);
	
	for(int i=0;i < n; i++)
	{
		for(int j = 0;j <n; j++)
		{
			scanf("%d",&map[i][j]);
			
			if(map[i][j]==2)
			{
				/// chicken
				a_chic[n_chic++] = make_pair(i,j);
			}
			if(map[i][j]==1)
			{
				a_house[n_house++] = make_pair(i,j);
			}
		}
	}
	
//	printf("n_chic : %d n_house : %d\n",n_chic,n_house);
}
int main()
{
	init();
	solve();
	printf("%d\n",min);
	return 0;
}

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

문제

문제

출처

ICPC

치킨 배달 문제 반례가 뭐가 있을까요?

smc3534 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말