Advertisement
alvsjo

C nedelja 5.

Mar 20th, 2018
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.08 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct ChessField
  5. {
  6.     int row;
  7.     int column;
  8.     int distance;
  9. };
  10.  
  11.  
  12. typedef ChessField QueueElem;
  13. struct Queue
  14. {
  15.     QueueElem* data;
  16. int front;
  17. int rear;
  18. int cap;
  19.  int size;
  20.  
  21.  
  22. };
  23.  
  24. typedef struct Queue Queue;
  25.  
  26. void initQueue( Queue* q, int c)
  27. {
  28.     q->data = malloc(sizeof(QueueElem)*c);
  29.     q->cap=c;
  30.     q->size=0;
  31.     q->front=0;
  32.     q->rear=-1;
  33. }
  34.  
  35. void destroyQueue (Queue *q)
  36. {
  37.     free(q->data);
  38.     free(q);
  39. }
  40.  
  41. int isEmpty(Queue *q)
  42. {
  43.     if(q->size==0)
  44.         return 1;
  45.     return 0;
  46. }
  47.  
  48. int isFull(Queue *q)
  49. {
  50.     if(q->size==q->cap)
  51.         return 1;
  52.     return 0;
  53. }
  54.  
  55. void enQueue(Queue *q, QueueElem a)
  56. {
  57.     if(isFull(q))
  58.     {
  59.         printf("Jam packed.\n");
  60.         return;
  61.     }
  62.  
  63.     q->rear=(q->rear+1)%q->cap;
  64.     q->size++;
  65.     q->data[q->rear]=a;
  66. }
  67.  
  68. QueueElem deQueue (Queue *q)
  69. {
  70.     if (isEmpty(q))
  71.     {
  72.         printf("Deserted.\n");
  73.         exit(1);
  74.     }
  75.     q->size--;
  76.     QueueElem temp=q->data[q->front];
  77.     q->front=(q->front+1)%q->cap;
  78.     return temp;
  79. }
  80.  
  81.  
  82. int in_table(int r, int c, int dx, int dy)
  83. {
  84.     if (r+dy>=0 && r+dy<8 && c+dx>=0 && c+dx<8)
  85.         return 1;
  86.     return 0;
  87. }
  88.  
  89.  
  90. int solve(int r1, int c1, int r2, int c2)
  91. {
  92.     Queue q;
  93.     initQueue(&q,10000);
  94.  
  95.     struct ChessField temp;
  96.     temp.row=r1;
  97.     temp.column=c1;
  98.     temp.distance=0;
  99.  
  100.     enQueue(&q,temp);
  101.  
  102.     int x[8]={1,-1,1,-1,2,-2,2,-2};
  103.     int y[8]={2,2,-2,-2,1,1,-1,-1};
  104.  
  105.     while(1)
  106.     {
  107.         temp = deQueue(&q);
  108.         if(temp.row == r2 && temp.column==c2)
  109.             return temp.distance;
  110.         int i;
  111.         for(i=0;i<8;i++)
  112.         {
  113.             if(in_table(temp.row,temp.column,x[i],y[i]))
  114.             {
  115.                 struct ChessField novi;
  116.                 novi.row=temp.row+y[i];
  117.                 novi.column=temp.column+x[i];
  118.                 novi.distance=temp.distance+1;
  119.                 enQueue(&q,novi);
  120.             }
  121.         }
  122.     }
  123. }
  124.  
  125.  
  126.  
  127.  
  128. int main()
  129. {
  130.     Queue q;
  131.     initQueue(&q,5);
  132.  
  133.  
  134.  
  135.  
  136.  
  137.     return 0;
  138. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement