paiza Qiita コラボ A問題 新都心のハイウェイ

A問題をSwiftでやりました。

問題概要

マス状のエリアにAとBがいる。縦横方向は見えるが斜めは見えない。エリアには障害物があり、障害物の向こうは見えない。AはBが見える位置に最小移動回数で移動する。

やり方

「Bの位置」がゴールではなく、「Bが見える位置」がゴールです。はじめにゴールをすべて設定します。いずれかのゴールに到達したら終了とします。

「進む」と「チェックする」の順番ですが、今回は初めからBが見える場合は一歩も動かずに終了するので、「チェックする」→「進む」の順番にしてコードをシンプルにします。

あとはAから「チェックする」→「進む」を繰り返しながら一歩ずつ進んでいきます。幅優先探索で行います。4歩でたどり着く場所を調べるときは、4歩でたどり着く場所をすべて調べてから5歩の場所の調査に移ります。

複数の経路で同じ場所にたどり着くことがあるので、2度調べないように工夫します。

たどり着かないときは-1を出力します。たどり着かないときの考慮を忘れないようにする。

import Foundation

func readInt() -> Int {
    Int(readLine()!)!
}

func readInts() -> [Int] {
    readLine()!.split(separator: " ").map { Int(String($0))! }
}

let hw = readInts()
let h = hw[0]
let w = hw[1]

var field: [[Character]] = []

for _ in 1...h {
    field.append(Array(readLine()!))
}

var aY = 0
var aX = 0
var bY = 0
var bX = 0

for y in 0..<h {
    for x in 0..<w {
        if field[y][x] == "A" {
            aX = x
            aY = y
        }
        if field[y][x] == "B" {
            bX = x
            bY = y
        }
    }
}

var target = [[Bool]](repeating: [Bool](repeating: false, count: w), count: h)

target[bY][bX] = true

var currentBY = bY
while currentBY + 1 <= h - 1 && field[currentBY + 1][bX] != "#" {
    currentBY += 1
    target[currentBY][bX] = true
}
currentBY = bY
while currentBY - 1 >= 0 && field[currentBY - 1][bX] != "#" {
    currentBY -= 1
    target[currentBY][bX] = true
}
var currentBX = bX
while currentBX + 1 <= w - 1 && field[bY][currentBX + 1] != "#" {
    currentBX += 1
    target[bY][currentBX] = true
}
currentBX = bX
while currentBX - 1 >= 0 && field[bY][currentBX - 1] != "#" {
    currentBX -= 1
    target[bY][currentBX] = true
}

var step = [[Int]](repeating: [Int](repeating: -1, count: w), count: h)
step[aY][aX] = 0

var checkPos: [(Int, Int)] = [(aY, aX)]

loop:
while true {
    var nextPos: [(Int, Int)] = []
    for p in checkPos {
        if target[p.0][p.1] {
            print(step[p.0][p.1])
            break loop
        }
        for (addY, addX) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
            let nY = p.0 + addY
            let nX = p.1 + addX
            if nY >= 0 && nY <= h - 1 && nX >= 0 && nX <= w - 1 {
                if field[nY][nX] != "#" && step[nY][nX] == -1 {
                    step[nY][nX] = step[p.0][p.1] + 1
                    nextPos.append((nY, nX))
                }
            }
        }
    }
    if nextPos.count == 0 {
        print(-1)
        break loop
    }
    checkPos = nextPos
}