C언어 BFS 미로 최단경로 구하기(escape the maze in C)

BFS 미로 최단경로

- DFS 알고리즘을 이용하여 주어진 미로의 최단 경로를 구하라.

제한 사항

- N X N 미로의 크기 N은 5 ~ 10

- 각 수행 시간은 10msec를 넘지 않도록 한다.

입력과 출력

- 입력은 맨 처음은 테스트 횟수(TC), 그 다음부터 N X N 미로의 크기 N 을 입력받고

미로의 원소들을 각각 입력받는다.( 입력은 첨부된 input.txt 파일을 이용한다. ) input.txt

시작점(1), 목표점(2), 길(0), 벽(7) = 이동할 수 없는 지점

- 출력은 우측의 출력 예를 참고한다.

입력 예	출력 예
5 5 7 1 7 7 7 7 0 0 0 7 7 0 7 0 7 7 7 0 0 7 7 7 7 2 7 .......	#1, ? msec. answer = 6 #2, ? msec. answer = 7 #3, ? msec. answer = 12 #4, ? msec. answer = 15 #5, ? msec. answer = 19

 

 

#include <stdio.h> #include <time.h> #include <malloc.h> #define NMAX 10 #define WALL 7 #define ROUTE 2 #define START 1 #define END  2 #define VISITED 3 typedef struct xy{  int x;  int y; }XY; typedef struct queue{  XY v;  struct queue *next; }QUEUE; int map[NMAX][NMAX]; int result; QUEUE *Q; XY s; void bfs( XY); void enqueue( XY); int queue_empty( void); XY dequeue( void); int main( void) {  time_t time_s, time_e;  int processtime;  int T,TC;  int N;  int i, j;  freopen("input.txt","r",stdin);  scanf("%d", &TC);  for( T = 0 ; T < TC ; T ++)  {   time_s = clock(); // get the starting time.   scanf("%d", &N);   for( i = 0 ; i < N ; i ++)   {    for( j = 0 ; j < N ; j ++)    {     scanf("%d", &map[i][j]);     // save the position of starting point.     if( map[i][j] == START)     {      s.y = i;      s.x = j;     }    }   }   result = -1;   bfs( s);   time_e = clock(); // get the ending time.   // calculate the time   processtime = (int)(time_e - time_s);   printf("#%d, %d msec. ",T+1 , processtime);   printf("answer = %d\n", result - VISITED);  }  return 0; } /*  enqueue()  it saves XY structure as the queue. */ void enqueue( XY v) {  QUEUE *temp = Q;  QUEUE *newq = (QUEUE*)malloc(sizeof(QUEUE));  newq->next = NULL;  newq->v  = v;  if( temp == NULL)  {   Q = newq;   return;  }  while( temp->next != NULL)  {   temp = temp->next;  }  temp->next = newq; } /*  queue_empty()  examine whether the queue is empty */ int queue_empty( void) {  return Q == NULL; } /*  dequeue()  get a element from the queue */ XY dequeue( void) {  QUEUE *temp = Q;  XY v;  v.x = temp->v.x;  v.y = temp->v.y;  Q = Q->next;  free(temp);  return v; } /*  bfs()  breadth fisrt search algorithm */ void bfs( XY s) {  XY v;  XY temp;  int i, j;  enqueue( s);  // mark this position as VISITED.  map[s.y][s.x] = VISITED;  while( !queue_empty())  {   v = dequeue();   // inspect the adjacency positions   for( i = v.y - 1 ; i < v.y + 2 ; i ++)   {    if( i < 0 ) continue; // if the position is off the map    for( j = v.x - 1 ; j < v.x + 2 ; j ++)    {     // check whether the position is on diagonal     if( abs( i - v.y ) == abs( j - v.x)) continue;     //  examine whether the position have ever visited.     if( map[i][j] >= VISITED) continue;     // if the position is the same with ending point.     if( map[i][j] == END)     {      result = map[v.y][v.x] + 1;      Q = NULL;      break;     }     // update weights of the routes     map[i][j] = map[v.y][v.x] + 1;     temp.x  = j;     temp.y  = i;     // add this position to the queue     enqueue( temp);    }   }  } }