UVA10496 Collecting Beepers

DFS, Graph

출처: UVA UVA10496 Collecting Beepers

SOL)

모든 경우를 탐색하여 가장 낮은 값을 찾고 출력..

[-] Collapse

#include<stdio.h>
#include<algorithm>
using namespace std;

int testCase, num;
int startX, startY;
int areaX, areaY;
int arr[12];
int result, temp;

struct pos{
    int x;
    int y;
};

pos info[13];

int dis(int l, int r){
    int x1 = info[l].x;
    int x2 = info[r].x;
    int y1 = info[l].y;
    int y2 = info[r].y;

    return abs(x1 - x2) + abs(y1 - y2);
}

void search(int idx){
    if (idx == num+1){
        if (result > temp)
            result = temp;
        return;
    }
    temp += dis(arr[idx], arr[idx + 1]);
    search(idx + 1);
}

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d", &testCase);
    while (testCase-- > 0){
        scanf("%d%d", &areaX, &areaY);
        scanf("%d%d", &startX, &startY);
        scanf("%d", &num);
        result = 1234567890;
        for (int i = 0; i < 12; i++)
            arr[i] = i + 1;
        for (int i = 2; i < num+2; i++)
            scanf("%d%d", &info[i].x, &info[i].y);
        info[1].x = startX;
        info[1].y = startY;
        info[num + 2].x = startX;
        info[num + 2].y = startY;
        arr[num + 1] = 1;
        do{
            temp = 0;
            search(0);
        } while (next_permutation(arr + 1, arr + 1 + num));

        printf("The shortest path has length %d\n", result);
    }
}