Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- struct ChessField
- {
- int row;
- int column;
- int distance;
- };
- typedef ChessField QueueElem;
- struct Queue
- {
- QueueElem* data;
- int front;
- int rear;
- int cap;
- int size;
- };
- typedef struct Queue Queue;
- void initQueue( Queue* q, int c)
- {
- q->data = malloc(sizeof(QueueElem)*c);
- q->cap=c;
- q->size=0;
- q->front=0;
- q->rear=-1;
- }
- void destroyQueue (Queue *q)
- {
- free(q->data);
- free(q);
- }
- int isEmpty(Queue *q)
- {
- if(q->size==0)
- return 1;
- return 0;
- }
- int isFull(Queue *q)
- {
- if(q->size==q->cap)
- return 1;
- return 0;
- }
- void enQueue(Queue *q, QueueElem a)
- {
- if(isFull(q))
- {
- printf("Jam packed.\n");
- return;
- }
- q->rear=(q->rear+1)%q->cap;
- q->size++;
- q->data[q->rear]=a;
- }
- QueueElem deQueue (Queue *q)
- {
- if (isEmpty(q))
- {
- printf("Deserted.\n");
- exit(1);
- }
- q->size--;
- QueueElem temp=q->data[q->front];
- q->front=(q->front+1)%q->cap;
- return temp;
- }
- int in_table(int r, int c, int dx, int dy)
- {
- if (r+dy>=0 && r+dy<8 && c+dx>=0 && c+dx<8)
- return 1;
- return 0;
- }
- int solve(int r1, int c1, int r2, int c2)
- {
- Queue q;
- initQueue(&q,10000);
- struct ChessField temp;
- temp.row=r1;
- temp.column=c1;
- temp.distance=0;
- enQueue(&q,temp);
- int x[8]={1,-1,1,-1,2,-2,2,-2};
- int y[8]={2,2,-2,-2,1,1,-1,-1};
- while(1)
- {
- temp = deQueue(&q);
- if(temp.row == r2 && temp.column==c2)
- return temp.distance;
- int i;
- for(i=0;i<8;i++)
- {
- if(in_table(temp.row,temp.column,x[i],y[i]))
- {
- struct ChessField novi;
- novi.row=temp.row+y[i];
- novi.column=temp.column+x[i];
- novi.distance=temp.distance+1;
- enQueue(&q,novi);
- }
- }
- }
- }
- int main()
- {
- Queue q;
- initQueue(&q,5);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement