163 lines
4.1 KiB
C
163 lines
4.1 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <stdbool.h>
|
|
#include "../include/labyrinth.h"
|
|
#include "../include/water.h"
|
|
#include "../include/priority_queue.h"
|
|
#include "../include/queue.h"
|
|
|
|
bool compare_water(coor* c1, coor* c2){
|
|
return c1->x < c2->x;
|
|
}
|
|
|
|
void pp(coor* c1){
|
|
printf("%d %d", c1->x, c1->y);
|
|
}
|
|
|
|
int qmin(queue* q);
|
|
|
|
void expand(coor* c, Labyrinth* labyrinth, queue* pq);
|
|
|
|
void water(Labyrinth *labyrinth){
|
|
int i, min;
|
|
|
|
queue(pq); // DA METTERE RBTREE (mai)
|
|
coor* tmp = (coor*)malloc(sizeof(coor));
|
|
tmp->x = labyrinth->start.x;
|
|
tmp->y = labyrinth->start.y;
|
|
labyrinth->at[tmp->x][tmp->y].dp = 0;
|
|
|
|
queuePush(pq, tmp);
|
|
pq->toString = pp; // TMP
|
|
|
|
queue(q);
|
|
q->toString = pp;
|
|
|
|
|
|
while(!queueIsEmpty(pq)){
|
|
printf("size: %d\n", pq->size);
|
|
queuePrint(pq);
|
|
|
|
min = qmin(pq);
|
|
printf("min: %d\n", min);
|
|
queue_element* qelem = pq->front;
|
|
queue_element* prev = NULL;
|
|
|
|
while(qelem){
|
|
|
|
printf("cons: ");
|
|
pp(qelem->element);
|
|
printf("\n");
|
|
if(((coor*)qelem->element)->x == min){
|
|
if(((coor*)(qelem->element))->x == labyrinth->end.x && ((coor*)(qelem->element))->y == labyrinth->end.y)
|
|
return;
|
|
|
|
printf("in elem: ");
|
|
pp(qelem->element);
|
|
printf("\n");
|
|
expand(qelem->element, labyrinth, q);
|
|
labyrinth->at[((coor*)qelem->element)->x][((coor*)qelem->element)->y].color = GREEN;
|
|
|
|
if(prev)
|
|
prev->next = qelem->next;
|
|
else
|
|
pq->front = qelem->next;
|
|
|
|
pq->size--;
|
|
|
|
if(!qelem->next)
|
|
pq->back = prev;
|
|
|
|
free(qelem->element);
|
|
free(qelem);
|
|
|
|
}else{
|
|
prev = qelem;
|
|
}
|
|
|
|
if(prev)
|
|
qelem = prev->next;
|
|
else if(pq->front)
|
|
qelem = pq->front->next;
|
|
else
|
|
qelem = NULL;
|
|
|
|
}
|
|
|
|
printf("newqueue: %d\n", pq->size);
|
|
queuePrint(pq);
|
|
printf("p: %d\n", q->size);
|
|
queuePrint(q);
|
|
|
|
queueMerge(pq, q);
|
|
printf("new: %d\n", pq->size);
|
|
queuePrint(pq);
|
|
|
|
printLab(labyrinth);
|
|
scanf("%d", &i);
|
|
}
|
|
}
|
|
|
|
|
|
void expand(coor* c, Labyrinth* labyrinth, queue* q){
|
|
int i = c->x, j = c->y;
|
|
|
|
if(i>0 && labyrinth->at[i-1][j].south && labyrinth->at[i-1][j].dp<0){
|
|
coor* tmp = (coor*)malloc(sizeof(coor));
|
|
tmp->x = i-1;
|
|
tmp->y = j;
|
|
|
|
queuePush(q, tmp);
|
|
|
|
labyrinth->at[i-1][j].direction = UP;
|
|
labyrinth->at[i-1][j].color = ORANGE;
|
|
labyrinth->at[i-1][j].dp = 0;
|
|
}
|
|
if(j<labyrinth->y_size-1 && labyrinth->at[i][j].east && labyrinth->at[i][j+1].dp<0){
|
|
coor* tmp = (coor*)malloc(sizeof(coor));
|
|
tmp->x = i;
|
|
tmp->y = j+1;
|
|
|
|
queuePush(q, tmp);
|
|
|
|
labyrinth->at[i][j+1].direction = UP;
|
|
labyrinth->at[i][j+1].color = ORANGE;
|
|
labyrinth->at[i][j+1].dp = 0;
|
|
}
|
|
if(i<labyrinth->x_size-1 && labyrinth->at[i][j].south && labyrinth->at[i+1][j].dp<0){
|
|
coor* tmp = (coor*)malloc(sizeof(coor));
|
|
tmp->x = i+1;
|
|
tmp->y = j;
|
|
|
|
queuePush(q, tmp);
|
|
|
|
labyrinth->at[i+1][j].direction = UP;
|
|
labyrinth->at[i+1][j].color = ORANGE;
|
|
labyrinth->at[i+1][j].dp = 0;
|
|
}
|
|
if(j>0 && labyrinth->at[i][j-1].east && labyrinth->at[i][j-1].dp<0){
|
|
coor* tmp = (coor*)malloc(sizeof(coor));
|
|
tmp->x = i;
|
|
tmp->y = j-1;
|
|
|
|
queuePush(q, tmp);
|
|
|
|
labyrinth->at[i][j-1].direction = UP;
|
|
labyrinth->at[i][j-1].color = ORANGE;
|
|
labyrinth->at[i][j-1].dp = 0;
|
|
}
|
|
}
|
|
|
|
|
|
int qmin(queue* q){
|
|
queue_element *tmp = q->front;
|
|
coor min = {.x = 0};
|
|
while(tmp){
|
|
if(compare_water(&min, tmp->element))
|
|
min.x = ((coor*)tmp->element)->x;
|
|
|
|
tmp = tmp->next;
|
|
}
|
|
|
|
return min.x;
|
|
} |