18-7. 第1回ビネクラ杯 ―ホルスへの道―

import numpy.random as nr

#============================
# ひとつのルートを見つける関数
#============================
def find_route(barrier, start, goal):
    #########################
    # 前処理
    #########################
    （中略）
    
    #########################
    # 幅優先探索
    #########################
    （中略）
    
    #++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    # 【追加】 ここで一旦終了判定、ゴールのコストが999であれば、ルートが見つかっていないので強制終了
    #++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
    （中略）
    
    #########################
    # ゴールから逆順でルート計算
    #########################
    point_now = goal
    cost_now = cost[goal[0], goal[1], goal[2]]
    route = [goal]
    #print('route\n{}'.format(route))
    while cost_now > 0:
        #来た可能性がある方向をすべてチェックする
        previous = []
        
        #x-から来た？
        try:
            if cost[point_now[0] - 1, point_now[1], point_now[2]] == cost_now - 1 and point_now[0] != 0:
                previous.append('x-')
        except: pass
        #x+から来た？
        try:
            if cost[point_now[0] + 1, point_now[1], point_now[2]] == cost_now - 1:
                previous.append('x+')
        except: pass
        #y-から来た？
        try:
            if cost[point_now[0], point_now[1] - 1, point_now[2]] == cost_now - 1 and point_now[1] != 0:
                previous.append('y-')
        except: pass
        #y+から来た？
        try:
            if cost[point_now[0], point_now[1] + 1, point_now[2]] == cost_now - 1:
                previous.append('y+')
        except: pass
        #z-から来た？
        try:
            if cost[point_now[0], point_now[1], point_now[2] - 1] == cost_now - 1 and point_now[2] != 0:
                previous.append('z-')
        except: pass
        #z+から来た？
        try:
            if cost[point_now[0], point_now[1], point_now[2] + 1] == cost_now - 1:
                previous.append('z+')
        except: pass
        
        #サイコロを振る
        dice = nr.randint(len(previous))
        #サイコロで出た方向を採用する
        direction = previous[dice]
        
        #その方向にトレースバック
        if direction == 'x-':
            #更新
            point_now = (point_now[0] - 1, point_now[1], point_now[2])
            cost_now = cost_now - 1
            #記録
            route.append(point_now)
            continue
        if direction == 'x+':
            point_now = (point_now[0] + 1, point_now[1], point_now[2])
            cost_now = cost_now - 1
            route.append(point_now)
            continue
        if direction == 'y-':
            point_now = (point_now[0], point_now[1] - 1, point_now[2])
            cost_now = cost_now - 1
            route.append(point_now)
            continue
        if direction == 'y+':
            point_now = (point_now[0], point_now[1] + 1, point_now[2])
            cost_now = cost_now - 1
            route.append(point_now)
            continue
        if direction == 'z-':
            point_now = (point_now[0], point_now[1], point_now[2] - 1)
            cost_now = cost_now - 1
            route.append(point_now)
            continue
        if direction == 'z+':
            point_now = (point_now[0], point_now[1], point_now[2] + 1)
            cost_now = cost_now - 1
            route.append(point_now)
            continue
    
    #ルートを逆順にする
    route = route[::-1]
    #print('route\n{}'.format(route))
    
    return route

#============================
# メイン処理（乱数シードを固定して、マンハッタン距離が短い順につなぐ、経路が見つからなかったら飛ばして次を探索する）
#============================

#乱数の固定
seed = 0
nr.seed(seed)

#通った場所（Falseで初期化）
barrier = np.zeros((20, 20, 20), dtype=bool)

#記録用の配列
score = 0
routes = []

#4000システム（発電機と装置の）のマンハッタン距離を求める
manhattan_dist = np.sum(np.abs(equipments - generators), axis=1)
print('manhattan_dist:\n{}'.format(manhattan_dist))

#マンハッタン距離の短い順に添え字を取得
manhattan_short_index = manhattan_dist.argsort()
print('manhattan_short_index:\n{}'.format(manhattan_short_index))

#一応、マンハッタン距離順に並び替えて表示してみる
print('manhattan_short:\n{}'.format(manhattan_dist[manhattan_short_index]))

for i in manhattan_short_index:
    print(i)
    
    #これからつなぐスタートやゴールが、すでに障害物となっていたら終わり
    if barrier[generators[i, 0], generators[i, 1], generators[i, 2]] == True:
        continue
    if barrier[equipments[i, 0], equipments[i, 1], equipments[i, 2]] == True:
        continue

    #ルートを見つける
    route = find_route(barrier, generators[i], equipments[i])
    
    #ルートが見つからなかったら終わり
    if route is None:
        continue
    else: #ルートが見つかったら、スコアを記録する
        score += 1
        routes.append(route)

    #通った場所を障害物とする
    for [x, y, z] in route:
        barrier[x, y, z] = True

#
print('score:\n{}'.format(score))
#print('routes:\n{}'.format(routes))

show_routes(routes)