글 읽기 - 치킨배달 시간초과

dhrzzah 2년 전 0

시간초과 뜨는데 어디서 시간초과 뜨는지 알려주세요

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <vector>

using namespace std;

int n;
int m;
int map[50][50];
int min_dis = 0x7fffffff;
bool visit[50][50];
vector <pair<int, int>> nene;
vector <pair<int, int>> home;

int calc()
{
	int sum = 0;
	vector<pair<int, int>> sel;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (visit[i][j] == true) {
				sel.push_back(pair<int, int>(i, j));
			}
		}
	}
	for (int i = 0; i < home.size(); i++) {
		int dis = 10000000;
		for (int j = 0; j < sel.size(); j++) {
			dis = min(abs(home[i].first - sel[j].first) + abs(home[i].second - sel[j].second), dis);
		}
		sum += dis;
	}
	return sum;
}
void dfs(int y,int x,int dep)
{	

	visit[y][x] = true;
	dep += 1;
	if (dep == m) {
		int temp = calc();
		min_dis = min(min_dis, temp);
	}
	else {
		for (int i = dep; i < nene.size(); i++) {
			if (visit[nene[i].first][nene[i].second] == false) dfs(nene[i].first, nene[i].second, dep);
		}
	}
	visit[y][x] = false;
	dep -= 1;
}
int main() 
{
	
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 2)
				nene.push_back(pair<int, int>(i, j));
			else if(map[i][j] == 1)
				home.push_back(pair<int, int>(i, j));
		}
	}
	
	for(int i=0;i<nene.size()-m+1;i++)
		dfs(nene[i].first,nene[i].second,0);
	cout << min_dis;
}

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

문제

문제

출처

ICPC

치킨배달 시간초과

dhrzzah 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말