与众不同的扫雷之二

继续扫雷

扫雷游戏中最核心的算法，当属显示空白区域的算法，当点中的方格位于一片空白区域之中时，游戏界面上要把这一片空白区域以及包围该区域的数字边界都显示出来。首先需要明确的一点是：包围空白区域的方格只可能为数字，不可能含有地雷，这个可以用反证法证明。

网上关于这个算法的实现，几乎都是低效地搜索相邻的空白区域，直到遇到数字边界为止，通常是用递归来实现的。我没有采用这种算法，从本能上我就排斥类似于这样的弱智算法。既然我采用字符串的形式来保存地图数据，理所当然的，我也应当利用 Lua 内置的高效字符串处理库来计算空白区。

另外，如果从效率上来考虑的话，最好是在第一次点击某块空格的时候，将所有的空白区域计算出来，并保存，以后每一次点击空格操作，就只需要查找点击的位置属于那一片空白区，然后显示出来即可。

思考算法实现的时候，单纯从数学的角度去考虑，未免枯燥了点。不妨把自己想象成一位具有非凡勇气的探险家，心怀梦想以及对未知世界的强烈渴望，驾驶着帆船航行于茫茫的大海，去探索新的海域，去发现新的大陆。嗯，再把时代背景安排在人类开始认识地球，观察宇宙，思考人生的文艺复兴时期，这样去思考算法就比较生动有趣了。

在我的每一次航行中，我都会到达许多未知的海域。为了能够探索到地球上全部的海域，我决定按照纬度，从零度经线开始向东行驶。每当完成一次环球旅行，我便向南行驶，到达一片新海域，然后继续从零度经线向东行驶，周而复始，直到探索完全部的海域，绘制一张精确的航海图，我的目的就达到了。

绘制一副精确的航海图是一件十分困难的事情，因为海洋是巨大而神秘的，而我们人类只是沧海一粟，为了将未知的海域逐一探索，首先，我要按照纬度，把海洋分成不同的海域。同一纬度上，连续不断的一片水域，我都把它们作为同一片海域对待。随着旅程不断增加，也许我会发现不同纬度的海域之间，它们在某一条或者多条经度线上，海水是互相连接着的，两片海域仿佛有海峡相连，这样，我就可以把这些水域在海图上全部划入相同的海域。最后，当我完成了全球探险之旅，我就可以知道，为陆地所包围着的海洋，或者说被海洋所包围着的陆地，究竟是什么样子的。某一片海洋，它的海面分布是从北纬多少，到南纬多少，从西经多少，到东经多少，我都会航海图上详细标明，一目了然。当有人想知道某一个经纬度已知的位置位于哪一片海洋，我就可以查看绘制好的航海图后，明确无误地告诉他了。



首先，我必须在海图上把相连的海域全部连成一片。

function classfy_sea_area(origin_map, current_map, width)
    local uncharted_water = split_sea_area(origin_map, current_map, width)
    local new_horizon = {}
    while #uncharted_water > 0 do
        local u_w = {}
        local sea_area = uncharted_water[1]
        for i, v in ipairs(uncharted_water) do
            if i > 1 then
                local n_h = has_strait_between(sea_area, v, width)
                if n_h then
                    sea_area = n_h
                else
                    u_w[#u_w + 1] = v
                end
            end
        end
        if #sea_area == #uncharted_water[1] then
            new_horizon[#new_horizon + 1] = sea_area
        else
            u_w[#u_w + 1] = sea_area
        end
        uncharted_water = u_w 
    end
    return new_horizon 
end

这样来划分海域。

function split_sea_area(origin_map, current_map, width)
    local col = 1
    local t3 = {}
    while true do
        local s1 = string.sub(origin_map, col, col + width - 1)
        local s2 = string.sub(current_map, col, col + width - 1)
        local i = 0
        local j = 0
        while true do
            i, j = string.find(s2, "?+", j + 1)
            if i == nil then break end
            local s = string.sub(s1, i, j)
            local off1 = 0
            local off2 = 0
            while true do
                off1, off2 = string.find(s, "0+", off2 + 1)
                if off1 == nil then break end
                local t1 = {}
                t1[#t1 + 1] = col + i + off1 - 2
                t1[#t1 + 1] = col + i + off2 - 2
                local t2 = {}
                t2[1] = t1
                t3[#t3 + 1] = t2
            end
        end
        col = col + width
        if col > #origin_map then
            break
        end
    end
    return t3
end

两片海域之间是否有海峡相邻？可以这样来判断：

function has_strait_between(sea_area1, sea_area2, width)
    for i1, v1 in ipairs(sea_area1) do
        for i2, v2 in ipairs(sea_area2) do
            local min_dist1 = v1[1] - v2[2] - 1
            local max_dist1 = v1[2] - v2[1] + 1
            local min_dist2 = v2[1] - v1[2] - 1
            local max_dist2 = v2[2] - v1[1] + 1
            if min_dist1 >= 0 then
                if (min_dist1 < width and width < max_dist1) 
                    or (min_dist1 == width and (v1[1] % width) ~= 1) 
                    or (max_dist1 == width and (v1[2] % width) ~= 0) then
                    return sea_area_union(sea_area1, sea_area2)
                end
            elseif min_dist2 >= 0 then
                if (min_dist2 < width and width < max_dist2) 
                    or (min_dist2 == width and (v2[1] % width) ~= 1) 
                    or (max_dist2 == width and (v2[2] % width) ~= 0) then
                    return sea_area_union(sea_area1, sea_area2)
                end
            end 
        end
    end
    return nil
end

如果发现两片海域属于同一个海洋，那么我需要在海图上把两片海域连起来

function sea_area_union(a, b)
    local c = {}
    for i,v in ipairs(a) do
        c[#c + 1] = v
    end
    for i,v in ipairs(b) do
        c[#c + 1] = v
    end
    return c
end