[1926] Nearest Exit from Entrance in Maze(TBD)

ㄜ..........怎麼這麼麻煩的題目XD

說是 enqueue的時候就要把它改成不能通過了！

dequeue再做就太慢了！ 比方說一個超大的矩陣只有四邊是牆，中間全部都是可以走的，

那就會重覆enqueue了！ 所以 QQ 

因為寫完好累了就先這樣吧Orz 先上個TBD 表示還沒有細看討論區XD！

typedef struct{

int x;

int y;

} Queue;

void printQ(Queue *q, int len)

{

for (int i=0;i<len; i++)

printf("q[%d] %d %d\n", i, q[i].x, q[i].y);

}

int enQueue(Queue *q, int x, int y, int tail)

{

q[tail].x=x;

q[tail].y=y;

return tail +1;

}

int en_fourQ(char** maze, Queue *q, int x, int y, int m, int n, int tail)

{

maze[x][y] = '+';

if ((x-1>=0) && (maze[x-1][y])=='.')

{

tail = enQueue(q,x-1, y, tail);

maze[x-1][y]= '+';

}

if ((x+1 < m) && (maze[x+1][y])=='.')

{

tail = enQueue(q,x+1, y, tail);

maze[x+1][y]= '+';

}

if ((y-1>=0) && (maze[x][y-1])=='.')

{

tail = enQueue(q,x, y-1, tail);

maze[x][y-1]= '+';

}

if ((y+1 < n) && (maze[x][y+1])=='.')

{

tail = enQueue(q,x, y+1, tail);

maze[x][y+1]= '+';

}

return tail;

}

int nearestExit(char** maze, int mazeSize, int* mazeColSize, int* entrance, int entranceSize) {

int thisround;

int head = 0, tail = 0;

int ret =0 ;

int m= mazeSize, n= (*mazeColSize) ;

Queue *myQ= calloc (40001, sizeof(Queue));

tail = enQueue(myQ,entrance[0], entrance[1], tail);

maze[entrance[0]][entrance[1]]='+';

while (head < tail)

{

thisround=tail;

for (int i=head; i<thisround;i++)

{

int _x= myQ[head].x; //dequeue one , and add at most four in this round

int _y= myQ[head].y;

if ((_x==0 || _x==m-1 || _y==0 || _y==n-1)

&& !(_x == entrance[0] && _y == entrance[1]))

{

return ret;

}

else

tail = en_fourQ(maze, myQ, _x, _y, m, n, tail);

head++;

}

ret++;

}

return (thisround >= 0)? (-1):ret;

}