#include "stdio.h" int ant_beep; int plass[2][21]; int brukt[21]; int lengde; int min_lengde; int niva; int a_x,a_y; int k_x,k_y; main() { int ant_runder; int i,j; int x_size,y_size; int b_x,b_y; scanf("%d\n",&ant_runder); for(i=1;i<=ant_runder;i++) { scanf("%d %d\n",&x_size,&y_size); scanf("%d %d \n",&k_x,&k_y); scanf("%d\n",&ant_beep); for(j=1;j<=ant_beep;j++) { scanf("%d %d \n",&b_x,&b_y); plass[0][j]= b_x; plass[1][j]= b_y; brukt[j] = 0; } min_lengde = 10000000; niva = ant_beep; lengde = 0; a_x = k_x; a_y = k_y; finn_tur(); printf("The shortest path has length %d\n",min_lengde); } } int finn_tur() { int i; int g_x,g_y; /* If at level 0, check if we have a new shortest path */ if (niva == 0) { lengde += abs(a_x - k_x) + abs(a_y - k_y); if (lengde < min_lengde) min_lengde = lengde; lengde -= abs(a_x - k_x) + abs(a_y - k_y); return; } /* Try each possible available beeper as the next one */ niva--; /* Keep current position */ g_x = a_x; g_y = a_y; for(i=1;i<=ant_beep;i++) { if (brukt[i] == 0) { /* Move to beeper number i */ brukt[i] = 1; lengde += abs(g_x - plass[0][i]) + abs(g_y - plass[1][i]); a_x = plass[0][i]; a_y = plass[1][i]; /* Finish the tour */ finn_tur(); /* Move back to current position */ a_x = g_x; a_y = g_y; lengde -= abs(g_x - plass[0][i]) + abs(g_y - plass[1][i]); brukt[i] = 0; } } niva++; }