2018-2-22 再练习广度优先搜索，题：炸怪兽
2小时。
先是是纠错，通过对代码运行过程的测试。发现是变量打错。以及录入地图❌。
重构练习题，改使用while..end代替for in.
⚠️ ： 在while（k <= n）中如果用到next，为了不陷入死♻️，注意条件的判断, 一般要在next前k += 1。
题：爆炸小子炸怪兽
代码：
# 地图
map = [
["#","#","#","#","#","#","#","#","#","#","#","#","#"],
["#","g","g",".","g","g","g","#","g","g","g",".","#"],
["#","#","#",".","#","g","#","g","#","g","#","g","#"],
["#",".",".",".",".",".",".",".","#",".",".","g","#"],
["#","g","#",".","#","#","#",".","#","g","#","g","#"],
["#","g","g",".","g","g","g",".","#",".","g","g","#"],
["#","g","#",".","#","g","#",".","#",".","#",".","#"],
["#","#","g",".",".",".","g",".",".",".",".",".","#"],
["#","g","#",".","#","g","#","#","#",".","#","g","#"],
["#",".",".",".","g","#","g","g","g",".","g","g","#"],
["#","g","#",".","#","g","#","g","#",".","#","g","#"],
["#","g","g",".","g","g","g","#","g",".","g","g","#"],
["#","#","#","#","#","#","#","#","#","#","#","#","#"]
]
# 地图副本book,用于标记走过的点。用compact复制出新的array。
# 因为不能嵌套复制。需要用map
book = map.map{|item| item.compact }
# 输出地图（对输出结果进行美化）
i = 0
n = map.size
n.times do |x|
print "#{x} "
end
print "\n"
while i < n
j= 0
while j < n
case map[i][j]
when "#"
print "◼︎ "
when "g"
print "☿ "
when "."
print " "
end
j += 1
end
print "\n"
i += 1
end
# 杀怪统计Method
def getnum(startx, starty, map)
# 四个方向各自统计杀怪数，加到sum中
sum = 0
x = y = 0
# 向下，遇到“#”，停止。（爆炸受阻）
x = startx
y = starty
while map[x][y] != "#"
if map[x][y] == "g"
sum += 1
end
x += 1
end
# 上
x = startx
y = starty
while map[x][y] != "#"
if map[x][y] == "g"
sum += 1
end
x -= 1
end
# 右
x = startx
y = starty
while map[x][y] != "#"
if map[x][y] == "g"
sum += 1
end
y += 1
end
# 左
x = startx
y = starty
while map[x][y] != "#"
if map[x][y] == "g"
sum += 1
end
y -= 1
end
return sum
end
# 设定开始起点位置
print "请输入起点坐标x:\n"
startx = gets.to_i
print "请输入起点坐标y:\n"
starty = gets.to_i
# wide first search
x = []
y = []
# 指针head , tail(队列最后一位的后面空白处)
head = 0
tail = 1
x[head] = startx
y[head] = starty
# 坐标点周边的四个方向,目的是访问相邻的4个点
next_direction = [
[0, 1],#右
[1, 0],#下
[0,-1],#左
[-1,0] #上
]
# 统计最大击杀
kill_max = 0
max_x = max_y = 0
# 边界的判断
nx = map[0].size - 2
ny = map.size - 2
# 大循环，wide first search
while head < tail
# 每个坐标点周边点的情况判定。
k = 0
while k <= 3
tx = x[head] + next_direction[k][0]
ty = y[head] + next_direction[k][1]
# 界限
if tx < 1 || tx > nx || ty <1 || ty > ny
# k += 1必不可少，否则会死循环。用for语法的话可以避免。
k += 1
next
end
# 判断是否是平地，而且没有走过
if map[tx][ty] == "." && book[tx][ty] == "."
# 在地图上标记已经走过
book[tx][ty] = "X"
x << tx
y << ty
# 队列尾巴的后一位，用于判断是否结束大循环
tail += 1
# 统计杀怪数量,调用Method
sum_kill = getnum(tx, ty, map)
if sum_kill > kill_max
kill_max = sum_kill
max_x = tx
max_y = ty
end
end
k += 1
end
# 头部指针前移动
head += 1
end
p "最大击杀#{kill_max}"
p "坐标：（#{max_x},#{max_y}）"