/****************************************/
队列运用）迷宫最短路径问题：
定义一个迷宫：
typedef std::pair<int, int> Pos;
int maze[7][9] = {
{-8, -8, -8, -8, -8, -8, -8, -8, -8},
{-8, -1, -8, -1, -1, -1, -8, -1, -8},
{-8, -1, -8, -1, -1, -1, -8, -1, -8},
{-8, -1, -8, -1, -8, -1, -8, -1, -8},
{-8, -1, -1, -1, -8, -1, -1, -1, -8},
{-8, -1, -1, -1, -8, -1, -1, -1, -8},
{-8, -8, -8, -8, -8, -8, -8, -8, -8},
};
最短路径解：
int shortest_path_len(Pos start, Pos dest) {
int len = 0;
maze[start.first][start.second] = len;
Queue<Pos> q;
q.push(start);
while(!q.empty()) {
int x = q.front().first;
int y = q.front().second;
len = maze[x][y];
if(dest.first == x && dest.second == y) //到达出口；
break;
q.pop();
if(maze[x+1][y] == -1 )
{ maze[x+1][y] = len + 1; q.push(Pos(x+1, y)); }
if(maze[x-1][y] == -1 )
{ maze[x-1][y] = len + 1; q.push(Pos(x-1, y)); }
if(maze[x][y+1] == -1 )
{ maze[x][y+1] = len + 1; q.push(Pos(x, y+1)); }
if(maze[x][y-1] == -1 )
{ maze[x][y-1] = len + 1; q.push(Pos(x, y-1)); }
}
return q.empty() ? -1 : len;
}
/****************************************************/
/**********************************************/
队列运用）数组基数排序实现：
#include "Queue.h"
enum{ radix = 10 };
typedef unsigned int T;
typedef Queue<T> QT;
void distribute(QT queues[], T const* first,
T const* last, int power) {
for(; first != last; ++first)
queues[(*first/power)%radix].push(*first);
}
void collect(T* first, QT queues[]) {
for(int digit = 0; digit < radix; ++digit)
while(!queues[digit].empty()) {
*first++ = queues[digit].front();
queues[digit].pop();
}
}
void radix_sort_10(T* first, T* last, int d = 10) {
QT queues[radix];
for(int pow = 1; --d >= 0; pow *= radix) {
distribute(queues, first, last, pow);
collect(first, queues);
}
}
