x,y 좌표로 징검다리있고


각 좌표 거리 2까지 떨어져있음 갈수있음


목표지점 y = F가 있는데

F에 도착하기까지 최단거리를 구해야하고

F 도착하기까지 적합한 루트 없으면 -1 출력해야함


그래서 내가 만든거임


--


#include <stdio.h>

#include <malloc.h>

#include <math.h>

#include <float.h>



typedef struct dot {

struct dot * node;

int x;

int y;

int offset;


}dot;


int * stack;






void mapping ( dot * graph,dot * temp, int N ){

int i,j;

int x,y;

dot * flag;

dot * in_flag;

in_flag= temp;

for(i=0;i<N;i++){

flag = graph+i ;

if( flag->x != temp->x || flag->y != temp->y ){ 

if( flag->x - temp->x <= 2 && flag->x - temp->x >= -2 && flag->y - temp->y <= 2 && flag->y - temp->y >= -2 ){

if( temp->node == NULL ){

temp->node = (dot*) malloc (sizeof(dot));

temp->node->x=flag->x;

temp->node->y=flag->y;

temp->node->offset=flag->offset;

temp->node->node=NULL;

}else{

while( temp->node != NULL ){

temp = temp->node;

}

temp->node = (dot*) malloc (sizeof(dot));

temp->node->x=flag->x;

temp->node->y=flag->y;

temp->node->offset=flag->offset;

temp->node->node=NULL;

}


temp = graph + temp->node->offset;


if(temp->node == NULL) {

temp->node = (dot*) malloc (sizeof(dot));

temp->node->x = in_flag->x;

temp->node->y = in_flag->y;

temp->node->offset = in_flag->offset;

temp->node->node = NULL;


}else{

while( temp->node != NULL ){

temp = temp->node;

}

temp->node = (dot*) malloc (sizeof(dot));

temp->node->x = in_flag->x;

temp->node->y = in_flag->y;

temp->node->offset = in_flag->offset;

temp->node->node = NULL;

}


temp = in_flag;


}

}

}

}



dot * make_graph(int N){


int i,j;

int x,y;

dot * graph = (dot*) malloc (sizeof(dot) * N);


for(i=0;i<N;i++){

scanf("%d %d", &x, &y);

( graph + i ) ->x =x;

( graph + i ) ->y =y;

( graph + i ) ->offset = i;

( graph + i ) ->node = NULL;

mapping(graph,graph + i,N);

}



return graph;


}




double final_length = DBL_MAX;

void DFS_Search ( dot * graph , dot * flag ,int F, double length_sum ) {

double x, y;

int i;

dot * start = flag;



if( flag->y >= F ){

if(final_length > length_sum){

final_length = length_sum;

}

}




while(flag->node != NULL){


if(stack[flag->node->offset]!=1){

stack[flag->node->offset] = 1;

x = flag->node->x - start->x;

y = flag->node->y - start->y;

if(x < 0 ){

x = -x;

}

if(y < 0 ){

y = -y;

}


DFS_Search(graph, graph + flag->node->offset ,F,length_sum + sqrt(pow(x,2) + pow(y,2)));

stack[flag->node->offset] = 0;

}

flag = flag->node;


}


}





int main(){


int N,F;

int i;

dot * graph;

dot * flag;


scanf("%d %d",&N,&F);

graph = make_graph(N);



stack = (int*) malloc (sizeof(int) * N);


for(i=0;i<N;i++){

if( stack[(graph+i)->offset] != 1){

if((graph+i)->x <=2 && (graph+i)->y <=2){

stack[(graph+i)->offset] =1;

DFS_Search(graph,graph,F,sqrt(pow((double)((graph+i)->x),2)+pow((double)((graph+i)->y),2)));

break;

}

}

}


if(final_length != DBL_MAX){

printf("%d\n",(int)(final_length + 0.5));

}else{

printf("%d\n",-1);

}



}


--


시간초과뜸 ^오^


이거보다 더 빠르겐 못만들거같은대