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

malmang 5년 전 0

어느부분을 고쳐야 할까요 ? 도와주세요ㅜ

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include<vector>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int n,m,ans=0;
int result=99999;
int ans2=99999;
int map[52][52];
int visit[52][52]={0,};
vector<pair<int,int>> chicken;
vector<pair<int,int>> home;
void street(){
    
}
void dfs(int c){
    if(c==m){
        ans=0;
        for(int i=0; i<home.size(); i++){
            result=99999;
            for(int ck=0; ck<m; ck++){
                int hr=home[i].first;
                int hc=home[i].second;
                int ckr=chicken[ck].first;
                int ckc=chicken[ck].second;
                result = min(abs(hr-ckr)+abs(hc-ckc),result);
            }
            ans = ans + result;
        }
        ans2 = min(ans2,ans);
        return;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(map[i][j]==2 && visit[i][j] !=1){
                chicken.push_back({i,j});
                visit[i][j]=1;
                dfs(c+1);
                visit[i][j]=0;
                chicken.pop_back();
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin>>map[i][j];
            if(map[i][j]==1){
                home.push_back({i,j});
            }
        }
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(map[i][j]==2 && visit[i][j]==0){
                chicken.push_back({i,j});
                visit[i][j]=1;
                dfs(1);
                visit[i][j]=0;
                chicken.pop_back();
            }
        }
    }
    cout<<ans2;


    return 0;
}

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

문제

문제

출처

ICPC

치킨배달 문제 시간초과..

malmang 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말