printf("%d\n", bfs(n));
}
}
return 0;
}
void enqueue(struct queue *Q, struct node p)
{
Q->data[Q->rear] = p;
Q->rear += 1;
Q->count += 1;
}
struct node dequeue(struct queue *Q)
{
struct node p;
p = Q->data[Q->front];
Q->front += 1;
Q->count -= 1;
return p;
}
int bfs(int n)
{
int i, tx, ty, tt;
struct node s, u, q;
// 初始化队列
struct queue *Q = (struct queue*)malloc(sizeof(struct queue));
Q->front = Q->rear = Q->count = 0;
// 首元素入队列
s.x = s.y = s.step = 0;
maze[0][0] = 1;
while (Q->count > 0) {
u = dequeue(Q);
if (u.x == n - 1 && u.y == n - 1) {
return u.step;
}
for (i = 0; i < 4; i ++) {
tx = u.x + dire[i][0];
ty = u.y + dire[i][1];
tt = u.step + 1;
if (tx >= 0 && ty >= 0 && tx < n && ty < n && maze[tx][ty] == 0) {
maze[tx][ty] = 1;
q.x = tx;
q.y = ty;
q.step = tt;
enqueue(Q, q);
}
}
}
return -1;
}
/**************************************************************
Problem: 1335
User: wangzhengyi
Language: C
Result: Accepted
Time:150 ms
Memory:3304 kb
****************************************************************/