二维数组中,如何判断某个元素被其它元素包围,请用lua写出代码
时间: 2024-03-28 17:41:24 浏览: 8
可以通过遍历二维数组,找到所有边缘的元素,然后以这些元素为起点,通过深度优先搜索或广度优先搜索,将与其相邻的所有元素标记为"不被包围"。最后再遍历一遍数组,如果发现还有未被标记的元素,则说明这个元素被包围了。
以下是用Lua实现的代码示例:
```lua
-- 定义一个函数,判断二维数组中的某个元素是否被包围
function isSurrounded(matrix, row, col)
local m, n = #matrix, #matrix[1]
local visited = {} -- 用一个矩阵记录哪些元素已经被标记过
for i = 1, m do
visited[i] = {}
for j = 1, n do
visited[i][j] = false
end
end
-- 定义一个递归函数,用于标记与当前元素相邻的所有元素
local function dfs(r, c)
visited[r][c] = true
if r > 1 and not visited[r-1][c] and matrix[r-1][c] == 0 then dfs(r-1, c) end
if r < m and not visited[r+1][c] and matrix[r+1][c] == 0 then dfs(r+1, c) end
if c > 1 and not visited[r][c-1] and matrix[r][c-1] == 0 then dfs(r, c-1) end
if c < n and not visited[r][c+1] and matrix[r][c+1] == 0 then dfs(r, c+1) end
end
-- 先从四个边缘开始搜索,标记与其相邻的所有元素
for i = 1, m do
if matrix[i][1] == 0 and not visited[i][1] then dfs(i, 1) end
if matrix[i][n] == 0 and not visited[i][n] then dfs(i, n) end
end
for j = 1, n do
if matrix[1][j] == 0 and not visited[1][j] then dfs(1, j) end
if matrix[m][j] == 0 and not visited[m][j] then dfs(m, j) end
end
-- 最后检查目标元素是否被标记,如果被标记则说明不被包围,否则被包围
return visited[row][col]
end
-- 测试
local matrix = {
{1, 1, 1, 1},
{1, 0, 0, 1},
{1, 0, 1, 1},
{1, 1, 1, 1}
}
print(isSurrounded(matrix, 2, 2)) -- 输出 true,因为(2,2)被包围
print(isSurrounded(matrix, 2, 3)) -- 输出 false,因为(2,3)不被包围
```