背景

有一只蚂蚁出去寻找食物，无意中进入了一个迷宫。蚂蚁只能向上、下、左、右4个方向走，迷宫中有墙和水的地方都无法通行。这时蚂蚁犯难了，怎样才能找出到食物的最短路径呢？

思路

蚂蚁想，假如我会影分身之术，我每一步都分成四个分身，向4个方向各走一步，这样最先找到食物的就是最短路径了（因为每一步都把能走的地方都走完了，肯定找不出更短的路径了）。

宽度优先搜索BFS

又称广度优先搜索，优先向四周扩展子节点，是最简便的图的搜索算法之一，一般通过队列来实现。

队列

是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作，即先进先出。
但上面的实现有一些缺陷，当队列满时，也就是tail指针移动到队尾，这时就无法再插入数据，但前面的元素已经出队了，可能还有空缺的位置。 为了能高效利用空间，对该队列增加一点改进，也就是循环队列的产生。

循环队列

把队列想象成一个首尾相接的环形。
数组实现，需要多预留一个空间。如果head=tail时，无法判断是队空还是队满，所以占用一个空间，通过tail+1与head的关系来判断是否队满。

队列实现BFS

-- 路径回溯
function printPath(start, target, visit)
    local curPos = target
    local path = {}
    while(true) do
        table.insert(path, curPos)
        if curPos == start then
            return path
        end
        local dir = visit[curPos]
        local x = curPos.x - dir[1]
        local y = curPos.y - dir[2]
        curPos = cc.p(x, y)
    end
end

function dfs()
    -- 队列
    local quene = {}
    -- 定义队列的最大长度
    local MAX_LEN = 1000    
    -- 方向向量
    local dirList = {       
        {0, 1},
        {-1, 0},
        {0, -1},
        {1, 0},
    }
    local head, tail = 1, 2
    local visit = {}    -- 记录访问的方向 用于回溯
    local start = cc.p(0, 0)
    local target = cc.p(999, 999)
    quene[head] = start
    while(true) do
        local curPos = quene[head]
        head = (head + 1)%MAX_LEN
        -- 4个方向
        for i = 1, 4 do
            local dir = dirList[i]
            local x = curPos.x + dir[1]
            local y = curPos.y + dir[2]
            local nextPos = cc.p(x, y)
            if not visit[nextPos] and isValid(nextPos) then
                visit[nextPos] = i
                if nextPos == target then
                    print("已到")
                    return printPath(start, target, visit)
                end
                if (tail + 1)%MAX_LEN == head then
                    print("队列已满")
                    return
                end
                quene[tail] = nextPos
                tail = (tail + 1)%MAX_LEN
            end
        end
    end
end