假设您被要求验证博物馆的安全性是否达到标准。您将获得一张地图,上面标有所有警卫和墙壁的位置:
4 6
0 0 g
0 1 w
1 1 g
2 2 w
2 3 g
第一行描述了博物馆的尺寸,它是一个 m x n 的矩形(本例中为 4 x 6),其中 m 和 n 始终大于 0。
随后的每一行对应警卫的位置(标记为"g")和墙壁的位置(标记为 "w")。例如,“0 0 g”表示在(0, 0)有一个警卫。
警卫不会移动,但可以保护以下任何一排的房间:
它们正好在北面、东面、南面或西面
其间没有阻挡(即它们之间没有墙)
例如,(0, 0)处的警卫只能看守 (1, 0), (2, 0) 和 (3, 0)。
然而(2,3)处的警卫可以看守 (0, 3), (1, 3), (2, 4), (2, 5)和 (3, 3)。
上述博物馆看起来像这样:
0 1 2 3 4 5
0 g w -
1 - g - - - -
2 - - w g - -
3 - - -
被保护的房间已用“-”标记。
给定一个博物馆,请按以下格式打印您的解决方案:
false
0 2
0 4
0 5
3 2
3 4
3 5
如果博物馆有未受保护的房间,则第一行应为“false”,如果博物馆没有未受保护的房间,则应为“true”。
如果是“false”,则后续行应该是未受保护的房间坐标。
未受保护的房间应以(x,y)的升序排列。
目前我尝试过的:
def checkUnguarded(arr, v)
i = 0
while i < arr.length do
j = 0
while j < arr[0].length do
if(arr[i][j]=='g')
r=i
c=j
k=r-1
while(k>=0&&(arr[k][c]=='w')) do
v[k][c]=true
k -= 1
end
k=r+1
while(k<arr.length&&(arr[k][c]=='w')) do
#binding.pry
v[k][c]=true
k += 1
end
k=c+1
while(k < arr[0].length && (arr[r][k]) == 'w') do
v[r][k]=true;
k += 1
end
k=c-1
while(k>=0 && (arr[r][k])=='w') do
v[r][k]=true
k -= 1
end
end
j += 1
end
i += 1
end
end
arr = [
[0, 0, 'g'],
[0, 1, 'w'],
[1, 1, 'g'],
[2, 2, 'w'],
[2, 3, 'g']
]
v = [
[0, 0],
[0, 0],
[0, 0],
[0, 0],
[0, 0],
]
puts(checkUnguarded(arr, v))
目前我正在尝试使用暴力破解方式。某些边缘情况失败了。