查找密切的路径或地区使用递归方法递归、路径、密切、地区
2023-09-11 23:17:17
作者：我的青春，从你爱我开始
我在二维数组一个对象，我想通过他们来遍历上，左，右的那个对象实际上可以我想检查是否有做一些循环或更好的做一些封闭区域。看到这个图片为更好的解释。
NOTE：事实上我有槽的X X Y和当任一区域的用户触摸它增加了砖有这样我想要做的是，每次用户添加一砖检查，如果这是有密切的路径。
我已经writen递归函数，该函数，但它不工作正常，它总是去的顶部，而不是只左右。这里是code
函数checkTrap（Y，X）
如果all_tiles [Y] [X] .state ==改变，那么 - - 如果砖块被添加在该位置
last_move_y = Y
last_move_x = X
--check顶级
Y = Y - 1
如果（γ＆GT; = 1并且Y = 6和（last_move_y〜= y或last_move_x〜= x）的），然后
打印（移动到顶部..Ÿ..，..x）
返回checkTrap（Y，X）
结束
--check的底部
Y = Y + 1
如果（γ＆GT; = 1并且Y = 6和（last_move_y〜= y或last_move_x〜= x）的），然后
打印（移到底部，在..Ÿ..，..x）
返回checkTrap（Y，X）
结束
- 检查左
X = X - 1
如果（X GT; = 1且X = 6和（last_move_y〜= y或last_move_x〜= x）的），然后
打印（迁留在..Ÿ..，..x）
返回checkTrap（Y，X）
结束
- 检查右
X = X + 1个
如果（X GT; = 1且X = 6和（last_move_y〜= y或last_move_x〜= x）的），然后
打印（向右移动，在..Ÿ..，..x）
返回checkTrap（Y，X）
结束
ELSEIF all_tiles [Y] [X] ==对象，然后
打印（这是一个循环..Ÿ..，..x）
返回true;
其他
打印（没有改变）
返回false
结束
结束
编辑：新的解决方案
函数findClosedRegion（）
当地currFlag，isClose = -1，假
当地isVisited = {
{-1，-1，-1，-1，-1，-1}，
{-1，-1，-1，-1，-1，-1}，
{-1，-1，-1，-1，-1，-1}，
{-1，-1，-1，-1，-1，-1}，
{-1，-1，-1，-1，-1，-1}，
{-1，-1，-1，-1，-1，-1}}
本地K，M = 1，1
而K＆LT; = 6，而不是isClose
做
打印（K..k）
而M＆LT; = 6，而不是isClose
做
打印（M..m）
如果不是isBrick [k]的[米]和isVisited [k]的[米] == -1然后
当地cellsi =堆栈：创建（）
当地cellsj =堆栈：创建（）
cellsi：推（K）
打印（推K..k）
cellsj：推（M）
打印（推M..m）
currFlag = currFlag + 1
isClose =真
而cellsi：getn（）＆GT; 0和isClose做
本地P = cellsi：POP（）
打印（流行P..p）
当地Q = cellsj：POP（）
打印（流行Q..q）
如果（P＆GT; = 1和P = 6且q＆GT; = 1且Q = 6），则
如果（不isBrick [P] [Q]），然后
打印（白）
如果（isVisited [P] [Q] == -1），那么
打印（invisited）
isVisited [P] [Q] = currFlag
cellsi.push（对 - 1）
cellsj.push（q）的
cellsi.push的（p + 1）
cellsj.push（q）的
cellsi.push（p）的
cellsj.push第（q + 1）
cellsi.push（p）的
cellsj.push（Q - 1）
cellsi：列表（）
其他
如果（isVisited [P] [Q]＆LT; currFlag），然后
打印（访问＆LT; currFlag）
isClose = FALSE
结束
结束
结束
其他
isClose = FALSE
结束--P和q，如果到此为止
结束 - 瓦而结束
其他
--print（改变，而不是-1）
结束
米= m + 1个
结束 - 米，而结束
如果（isClose），然后
打印（闭合路径）
结束
m = 1时
K = K + 1
结束 - K，而结束
结束
解决方案
EDITED ： 相反，如果有黑色细胞的帮助下寻找，我们应该有白细胞搜索，因为你的目标是要找到面积约束的黑色细胞，即使对角相邻。我们应该找到一组白细胞仅由黑单元，而不是由整个主网格的边界毗邻。这应该满足你的目的。
JS小提琴： http://jsfiddle.net/4d4wqer2/
这是修改后的算法，我想出了：
为每个小区，直到封闭区域未发现
如果白visitedValue = -1
推动电池堆栈
而栈具有价值和封闭区域未发现
从堆栈中弹出电池
如果无效的单元格//单元格的坐标无效
此区域未关闭，所以从而破
其他
如果白
如果visitedValue = -1
{
马克参观
推相邻的四个小区到堆栈
}
其他
如果visitedValue＆GT; currVisitNumber //目前的细胞是previous部分搜索电池组，这是不是一个封闭的群体。
此区域未关闭，所以从而破
如果禁区发现
展会信息
使用JQuery编程：
函数findArea（）{
VAR currFlag = -1，isvisited = []，isClosed返= FALSE;
为（变种K = 0; K＆LT;行; k ++）{//初始化isvisited阵列
isvisited [K] = [];
对于（VAR M = 0; M＆LT; COLS; M +）
isvisited [k]的[米] = -1;
}
为（变种K = 0; K＆LT;行和放大器;＆安培;！isClosed返; k ++）
对于（VAR M = 0; M＆LT; COLS和放大器;＆安培;！isClosed返; M +）{
如果（isblack [k]的[米]安培;！＆安培; isvisited [k]的[米] == - 1）{//未访问的白细胞
VAR cellsi = [K]，cellsj = [M]。
currFlag ++;
isClosed返= TRUE;
而（cellsi.length大于0＆安培;＆安培; isClosed返）{//堆栈具有细胞和没有封闭区域被发现
变种p值= cellsi.pop（）中，q = cellsj.pop（）;
如果（P＆GT; = 0＆功放;＆安培; P＆LT;行和放大器;＆安培; Q＆GT; = 0＆功放;＆安培; Q＆LT; COLS）{//细胞coord.s是有效的
如果（！isblack [P] [Q]）
如果（isvisited [P] [Q] == -1）{
isvisited [P] [Q] = currFlag; //马克参观
cellsi.push（对 - 1）; //推四个相邻小区的coord.s
cellsj.push（q）的;
cellsi.push的（p + 1）;
cellsj.push（q）的;
cellsi.push（对）;
cellsj.push第（q + 1）;
cellsi.push（对）;
cellsj.push（Q - 1）;
}
其他
如果（isvisited [P] [Q]＆其中; currFlag）//白细胞当前组这被认为是未结合的由黑单元一个previous组白细胞的一部分。所以，请跳过此组。
isClosed返= FALSE;
}
其他
isClosed返= FALSE; //将当前单元格超出边界。因此跳过了整个集团。
}
}
}
如果（isClosed返）
警报（'禁区找到'）;
}
JS小提琴： http://jsfiddle.net/4d4wqer2/
I have a object in 2d array and i want to traverse through them top, left, right for that object acutally i want to check if there are making some loop or better making some closed region. See this picture for better explanation.
Acutally i have a X x Y of slot and when user touch on any of the region it adds the brick there so what i want to do is every time user add a brick check if it is making a close path.
I have writen recursive function for that but it's not working fine it always go for the top only and not right and left. Here is the code
function checkTrap(y,x)
if all_tiles[y][x].state == "changed" then --if brick is added at that location
last_move_y = y
last_move_x = x
--check for top
y = y - 1
if( y >= 1 and y <= 6 and (last_move_y ~= y or last_move_x ~= x) ) then
print("Moved to top at"..y..", "..x)
return checkTrap(y, x)
end
--check for bottom
y = y + 1
if( y >= 1 and y <= 6 and (last_move_y ~= y or last_move_x ~= x) ) then
print("Moved to bottom at"..y..", "..x)
return checkTrap(y, x)
end
--check for left
x = x - 1
if( x >= 1 and x <= 6 and (last_move_y ~= y or last_move_x ~= x) ) then
print("Moved to left at"..y..", "..x)
return checkTrap(y, x)
end
--check for right
x = x + 1
if( x >= 1 and x <= 6 and (last_move_y ~= y or last_move_x ~= x) ) then
print("Moved to right at"..y..", "..x)
return checkTrap(y, x)
end
elseif all_tiles[y][x] == object then
print("it's a loop"..y..", "..x)
return true;
else
print("not changed")
return false
end
end
Edit : New Solution
function findClosedRegion()
local currFlag, isClose = -1, false
local isVisited = {
{-1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1},
{-1, -1, -1, -1, -1, -1}}
local k, m = 1, 1
while k <= 6 and not isClose
do
print("K "..k)
while m <= 6 and not isClose
do
print("M "..m)
if not isBrick[k][m] and isVisited[k][m] == -1 then
local cellsi = Stack:Create()
local cellsj = Stack:Create()
cellsi:push(k)
print("Pushed k "..k)
cellsj:push(m)
print("Pushed m "..m)
currFlag = currFlag + 1
isClose = true
while cellsi:getn() > 0 and isClose do
local p = cellsi:pop()
print("Pop p "..p)
local q = cellsj:pop()
print("Pop q "..q)
if( p >= 1 and p <= 6 and q >= 1 and q <= 6 ) then
if(not isBrick[p][q]) then
print("white ")
if(isVisited[p][q] == -1) then
print("invisited")
isVisited[p][q] = currFlag
cellsi.push(p - 1)
cellsj.push(q)
cellsi.push(p + 1)
cellsj.push(q)
cellsi.push(p)
cellsj.push(q + 1)
cellsi.push(p)
cellsj.push(q - 1)
cellsi:list()
else
if(isVisited[p][q] < currFlag) then
print("visited < currFlag")
isClose = false
end
end
end
else
isClose = false
end --p and q if ends here
end -- tile while end
else
--print("changed and not -1")
end
m = m + 1
end -- m while end
if(isClose) then
print("Closed path")
end
m = 1
k = k + 1
end -- k while end
end
解决方案
EDITED: Instead if searching with the help of black cells, we should search with white cells because your goal is to find area bound by black cells, even if diagonally adjacent. We should find a group of white cells which is only bordered by black cells and not by the border of the whole main grid. That should satisfy your purpose.
JS Fiddle: http://jsfiddle.net/4d4wqer2/
This is the revised algorithm I came up with:
for each cell and until closed area not found
if white and visitedValue = -1
push cell to stack
while stack has values and closed area not found
pop cell from stack
if invalid cell // Cell coordinates are invalid
this area is not closed, so break from the while
else
if white
if visitedValue = -1
{
mark visited
push neighboring four cells to the stack
}
else
if visitedValue > currVisitNumber // The current cells are part of previous searched cell group, which was not a closed group.
this area is not closed, so break from the while
if closed area found
show message
Programmed using JQuery:
function findArea() {
var currFlag = -1, isvisited = [], isClosed = false;
for (var k = 0; k < rows; k++) { // Initialize the isvisited array
isvisited[k] = [];
for (var m = 0; m < cols; m++)
isvisited[k][m] = -1;
}
for (var k = 0; k < rows && !isClosed; k++)
for (var m = 0; m < cols && !isClosed; m++) {
if (!isblack[k][m] && isvisited[k][m] == -1) { // Unvisited white cell
var cellsi = [k], cellsj = [m];
currFlag++;
isClosed = true;
while (cellsi.length > 0 && isClosed) { // Stack has cells and no closed area is found
var p = cellsi.pop(), q = cellsj.pop();
if (p >= 0 && p < rows && q >= 0 && q < cols) { // The cell coord.s are valid
if (!isblack[p][q])
if (isvisited[p][q] == -1) {
isvisited[p][q] = currFlag; // Mark visited
cellsi.push(p - 1); // Push the coord.s of the four adjacent cells
cellsj.push(q);
cellsi.push(p + 1);
cellsj.push(q);
cellsi.push(p);
cellsj.push(q + 1);
cellsi.push(p);
cellsj.push(q - 1);
}
else
if (isvisited[p][q] < currFlag) // The current group of white cells was part of a previous group of white cells which were found to be unbound by the black cells. So, skip this group.
isClosed = false;
}
else
isClosed = false; // The current cell is out of border. Hence skip the whole group.
}
}
}
if (isClosed)
alert('Closed area found');
}
JS Fiddle: http://jsfiddle.net/4d4wqer2/
相关推荐
猜您喜欢
精彩图集
