글 읽기 - 시간을 줄일 수 있는 방법이 뭐가 있을까요...

sagjin0000 3년 전 1

계속 시간초과가 뜨는데 시간을 줄일 방법이 생각이 안나네요...

#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

int N, M;
int ans = 987654321;
int city[51][51];
vector<pii> house;
vector<pii> chicken;
vector<pii> checked;

void input(){
    scanf("%d %d", &N, &M);

    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j){
            scanf("%d", &city[i][j]);

            if(city[i][j] == 1) house.push_back(make_pair(i, j));

            if(city[i][j] == 2) chicken.push_back(make_pair(i, j));
        }
}

void chickenstreet(){
    int sum = 0;
    for(int i = 0; i < house.size(); ++i){
        pii h = house[i];
        int tmp = 98765432;
        for(int j = 0; j < checked.size(); ++j){
            pii c = checked[j];
            int street = abs(c.first - h.first) + abs(c.second - h.second);
            tmp = street < tmp ? street : tmp;
        }
        sum += tmp;
    }
    ans = sum < ans ? sum : ans;
}

void dfs(int x){
    if(checked.size() == M) {
        chickenstreet();
        return;
    }

    for(int i = x; i < chicken.size(); ++i){
        checked.push_back(chicken[i]);
        dfs(x + 1);
        checked.pop_back();
    }
}

void solution(){
    dfs(0);
}

void output(){
    printf("%d\n", ans);
}

int main(void) {
    input();
    solution();
    output();

    return 0;
}