【電脳少女プログラミング2088 ─壊レタ君を再構築─】「新都心のハイウェイ」をやってみた。

paizaの新作プログラミングゲーム【電脳少女プログラミング2088 ─壊レタ君を再構築─】[新都心のハイウェイ（paizaランク：A相当）](https://ppg.paiza.jp/denno2088/areas/11)をやってみました。
###### 問題
https://ppg.paiza.jp/denno2088/challenges/denno2088_c_a_01
- - -
###### 方針
[幅優先探索](https://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2)を使います。
ゴールとして、「Bの上下左右方向の壁マスに当たるまでの全てのマス」を設定します。
![highway.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3634253/e80d63fc-02aa-153b-72f8-7175dbab7bdd.png)
- - -
###### C
```c
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

const int D[][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

/*
	幅優先探索
*/
int bfs(int h, int w, char *s[]) {
	// ゴール（falseで初期化）
	bool goal[h][w];
	memset(goal, false, sizeof(goal));

	// 最小移動回数（大きな値で初期化）
	int cost[h][w];
	memset(cost, 0x7F, sizeof(cost));

	// Aの初期位置を(-1, -1)で初期化
	int y = -1;
	int x = -1;

	// マスの情報を受け取る
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (s[i][j] == 'A') { // Aの初期位置
				y = i;
				x = j;
				cost[i][j] = 0; // 初期位置への最小移動回数は0
			} else if (s[i][j] == 'B') { // Bの位置
				// Bの位置はゴール（本問ではここに到達することはないが）
				goal[i][j] = true;
				
				// Bの位置から右方向に、壁マスの直前までゴールを設定する
				for (int k = j + 1; k < w; k++) {
					if (s[i][k] == '#') break;
					goal[i][k] = true;
				}
				
				// Bの位置から下方向に、壁マスの直前までゴールを設定する
				for (int k = i + 1; k < h; k++) {
					if (s[k][j] == '#') break;
					goal[k][j] = true;
				}
				
				// Bの位置から左方向に、壁マスの直前までゴールを設定する
				for (int k = j - 1; k >= 0; k--) {
					if (s[i][k] == '#') break;
					goal[i][k] = true;
				}
				
				// Bの位置から上方向に、壁マスの直前までゴールを設定する
				for (int k = i - 1; k >= 0; k--) {
					if (s[k][j] == '#') break;
					goal[k][j] = true;
				}
			} else if (s[i][j] == '#') { // 壁マス
				// 壁マスへの最小移動回数を負の値に設定しておく
				cost[i][j] = -1;
			}
		}
	}

	// 既にBを見つけられている場合は0を返却する
	if (goal[y][x]) return cost[y][x];

	// キュー構造を配列で実装
	int Q[h*w][2]; // キューの要素はint[2]
	int back = 0;
	int front = 0;

	// キューに初期位置を格納
	Q[back][0] = y;
	Q[back][1] = x;
	back++;
	
	while (back > front) { // キューが空でない間
		// キューから取り出す
		y = Q[front][0];
		x = Q[front][1];
		front++;

		// 現在位置への最小移動回数+1が隣のマスへの最小移動回数
		int c = cost[y][x] + 1;
		
		for (int k = 0; k < 4; k++) {
			int i = y + D[k][0];
			int j = x + D[k][1];
			if (0 <= i && i < h && 0 <= j && j < w) {
				// Bを見つけることができた場合、終了
				if (goal[i][j]) return c;
				
				if (cost[i][j] > c) { // 未探索
					cost[i][j] = c;

					// キューに格納
					Q[back][0] = i;
					Q[back][1] = j;
					back++;
				}
			}
		}
	}

	// Bを見つけることができない場合は-1を返却
	return -1;
}

int main() {
	int H, W;
	scanf("%d %d", &H, &W);
	char S[H][W+1];
	char *p[H]; //　関数に渡す為の文字配列へのポインタ
	for (int i = 0; i < H; i++) {
		scanf("%s", S[i]);
		p[i] = S[i];
	}
	printf("%d\n", bfs(H, W, p));
	return 0;
}
```
- - -
###### C++
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <tuple>
using namespace std;

const vector<pair<int, int>> D = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

int bfs(int h, int w, const vector<string> &s) {
	vector<vector<bool>> goal(h, vector<bool>(w, false));
	vector<vector<int>> cost(h, vector<int>(w, INT32_MAX));
	int y, x;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (s[i][j] == 'A') {
				y = i;
				x = j;
				cost[i][j] = 0;
			} else if (s[i][j] == 'B') {
				goal[i][j] = true;
				for (int k = j + 1; k < w; k++) {
					if (s[i][k] == '#')
						break;
					goal[i][k] = true;
				}
				for (int k = i + 1; k < h; k++) {
					if (s[k][j] == '#')
						break;
					goal[k][j] = true;
				}
				for (int k = j - 1; k >= 0; k--) {
					if (s[i][k] == '#')
						break;
					goal[i][k] = true;
				}
				for (int k = i - 1; k >= 0; k--) {
					if (s[k][j] == '#')
						break;
					goal[k][j] = true;
				}
			} else if (s[i][j] == '#') {
				cost[i][j] = -1;
			}
		}
	}
	if (goal[y][x])
		return cost[y][x];
	queue<pair<int, int>> Q;
	Q.push( { y, x });
	while (!Q.empty()) {
		tie(y, x) = Q.front();
		Q.pop();
		int c = cost[y][x] += 1;
		for (pair<int, int> d : D) {
			int i = y + d.first;
			int j = x + d.second;
			if (0 <= i && i < h && 0 <= j && j < w) {
				if (goal[i][j])
					return c;
				if (cost[i][j] > c) {
					cost[i][j] = c;
					Q.push( { i, j });
				}
			}
		}
	}
	return -1;
}

int main() {
	int H, W;
	cin >> H >> W;
	vector<string> S(H);
	for (int i = 0; i < H; i++)
		cin >> S[i];
	cout << bfs(H, W, S) << endl;
	return 0;
}
```
- - -
###### C#
```cs
using System;
using System.Collections.Generic;

class Program
{
	static readonly int[][] D = new int[][] { new int[] { 0, 1 }, new int[] { 1, 0 }, new int[] { 0, -1 }, new int[] { -1, 0 } };

	private static int BFS(int h, int w, string[] s)
	{
		bool[][] goal = new bool[h][];
		int[][] cost = new int[h][];
		for (int i = 0; i < h; i++)
		{
			goal[i] = new bool[w];
			cost[i] = new int[w];
			for (int j = 0; j < w; j++)
			{
				goal[i][j] = false;
				cost[i][j] = int.MaxValue;
			}
		}
		int y = -1; int x = -1;
		for (int i = 0; i < h; i++)
		{
			for (int j = 0; j < w; j++)
			{
				if (s[i][j] == 'A')
				{
					y = i;
					x = j;
					cost[i][j] = 0;
				}
				else if (s[i][j] == 'B')
				{
					goal[i][j] = true;
					for (int k = j + 1; k < w; k++)
					{
						if (s[i][k] == '#') break;
						goal[i][k] = true;
					}
					for (int k = i + 1; k < h; k++)
					{
						if (s[k][j] == '#') break;
						goal[k][j] = true;
					}
					for (int k = j - 1; k >= 0; k--)
					{
						if (s[i][k] == '#') break;
						goal[i][k] = true;
					}
					for (int k = i - 1; k >= 0; k--)
					{
						if (s[k][j] == '#') break;
						goal[k][j] = true;
					}
				}
				else if (s[i][j] == '#')
				{
					cost[i][j] = -1;
				}
			}
		}
		if (goal[y][x]) return cost[y][x];
		Queue<int[]> Q = new Queue<int[]>();
		Q.Enqueue(new int[] { y, x });
		while (Q.Count > 0)
		{
			int[] q = Q.Dequeue();
			y = q[0];
			x = q[1];
			int c = cost[y][x] + 1;
			foreach (int[] d in D)
			{
				int i = y + d[0];
				int j = x + d[1];
				if (0 <= i && i < h && 0 <= j && j < w)
				{
					if (goal[i][j]) return c;
					if (cost[i][j] > c)
					{
						cost[i][j] = c;
						Q.Enqueue(new int[] { i, j });
					}
				}
			}
		}
		return -1;
	}

	public static void Main()
	{
		int[] hw = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
		int H = hw[0];
		int W = hw[1];
		string[] S = new string[H];
		for (int i = 0; i < H; i++)
		{
			S[i] = Console.ReadLine();
		}
		Console.WriteLine(BFS(H, W, S));
	}
}
```
- - -
###### Go
```go
package main
import "fmt"

var D = [][]int{ { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }

func bfs(h int, w int, s []string) int {
	goal := make([][]bool, h)
	cost := make([][]int, h)
	for i := 0; i < h; i++ {
		goal[i] = make([]bool, w)
		cost[i] = make([]int, w)
		for j := 0; j < w; j++ {
			goal[i][j] = false
			cost[i][j] = 0x7FFFFFFF
		}
	}
	var y int
	var x int
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			if s[i][j] == 'A' {
				y = i
				x = j
				cost[i][j] = 0
			} else if s[i][j] == 'B' {
				goal[i][j] = true
				for k := j + 1; k < w; k++ {
					if s[i][k] == '#' {
						break
					}
					goal[i][k] = true
				}
				for k := i + 1; k < h; k++ {
					if s[k][j] == '#' {
						break
					}
					goal[k][j] = true
				}
				for k := j - 1; k >= 0; k-- {
					if s[i][k] == '#' {
						break
					}
					goal[i][k] = true
				}
				for k := i - 1; k >= 0; k-- {
					if s[k][j] == '#' {
						break
					}
					goal[k][j] = true
				}
				
			} else if s[i][j] == '#' {
				cost[i][j] = -1
			}
		}
	}
	if goal[y][x] {
		return cost[y][x]
	}
	Q := [][]int{}
	Q = append(Q, []int{ y, x })
	for len(Q) > 0 {
		q := Q[0]
		Q = Q[1:]
		y = q[0]
		x = q[1]
		c := cost[y][x] + 1
		for k := 0; k < len(D); k++ {
			i := y + D[k][0]
			j := x + D[k][1]
			if 0 <= i && i < h && 0 <= j && j < w {
				if goal[i][j] {
					return c
				}
				if cost[i][j] > c {
					Q = append(Q, []int{ i, j })
					cost[i][j] = c
				}
			}
		}
	}
	return -1
}

func main(){
	var H, W int
	fmt.Scan(&H, &W)
	S := make([]string, H)
	for i := 0; i < H; i++ {
		fmt.Scan(&S[i])
	}
	
	fmt.Println(bfs(H, W, S))
}
```
- - -
###### Java
```java
import java.util.*;

public class Main {

	static final int[][] D = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };

	private static int bfs(int h, int w, String[] s) {
		boolean[][] goal = new boolean[h][];
		int[][] cost = new int[h][];
		for (int i = 0; i < h; i++) {
			goal[i] = new boolean[w];
			cost[i] = new int[w];
			for (int j = 0; j < w; j++) {
				goal[i][j] = false;
				cost[i][j] = Integer.MAX_VALUE;
			}
		}
		int y = -1;
		int x = -1;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (s[i].charAt(j) == 'A') {
					y = i;
					x = j;
					cost[i][j] = 0;
				} else if (s[i].charAt(j) == 'B') {
					goal[i][j] = true;
					for (int k = j + 1; k < w; k++) {
						if (s[i].charAt(k) == '#')
							break;
						goal[i][k] = true;
					}
					for (int k = i + 1; k < h; k++) {
						if (s[k].charAt(j) == '#')
							break;
						goal[k][j] = true;
					}
					for (int k = j - 1; k >= 0; k--) {
						if (s[i].charAt(k) == '#')
							break;
						goal[i][k] = true;
					}
					for (int k = i - 1; k >= 0; k--) {
						if (s[k].charAt(j) == '#')
							break;
						goal[k][j] = true;
					}
				} else if (s[i].charAt(j) == '#') {
					cost[i][j] = -1;
				}
			}
		}
		if (goal[y][x])
			return cost[y][x];

		Queue<Integer[]> Q = new ArrayDeque<Integer[]>();
		Q.add(new Integer[] { y, x });
		while (!Q.isEmpty()) {
			Integer[] q = Q.remove();
			y = q[0];
			x = q[1];
			int c = cost[y][x] + 1;
			for (int[] d : D) {
				int i = y + d[0];
				int j = x + d[1];
				if (0 <= i && i < h && 0 <= j && j < w) {
					if (goal[i][j])
						return c;
					if (cost[i][j] > c) {
						cost[i][j] = c;
						Q.add(new Integer[] { i, j });
					}
				}
			}
		}
		return -1;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		String[] S = new String[H];
		for (int i = 0; i < H; i++)
			S[i] = sc.next();
		System.out.println(bfs(H, W, S));
		sc.close();
	}
}
```
- - -
###### JavaScript
```js
const D = [[0, 1], [1, 0], [0, -1], [-1, 0]];

function bfs(h, w, s) {
	let goal = Array.from({ length: h }, () => Array(w).fill(false));
	let cost = Array.from({ length: h }, () => Array(w).fill(Number.MAX_SAFE_INTEGER));
	let y = -1;
	let x = -1;
	for (var i = 0; i < h; i++) {
		for (var j = 0; j < w; j++) {
			if (s[i][j] === 'A') {
				y = i;
				x = j;
				cost[i][j] = 0;
			} else if (s[i][j] === 'B') {
				goal[i][j] = true;
				for (var k = j + 1; k < w; k++) {
					if (s[i][k] === '#')
						break;
					goal[i][k] = true;
				}
				for (var k = i + 1; k < h; k++) {
					if (s[k][j] === '#')
						break;
					goal[k][j] = true;
				}
				for (var k = j - 1; k >= 0; k--) {
					if (s[i][k] === '#')
						break;
					goal[i][k] = true;
				}
				for (var k = i - 1; k >= 0; k--) {
					if (s[k][j] === '#')
						break;
					goal[k][j] = true;
				}
			} else if (s[i][j] === '#') {
				cost[i][j] = -1;
			}
		}
	}
	if (goal[y][x])
		return cost[y][x];

	Q = [[y, x]]
	while (Q.length) {
		[y, x] = Q.shift();
		const c = cost[y][x] + 1;
		for (k = 0; k < D.length; k++) {
			const i = y + D[k][0];
			const j = x + D[k][1];
			if (0 <= i && i < h && 0 <= j && j < w) {
				if (goal[i][j])
					return c;
				if (cost[i][j] > c) {
					cost[i][j] = c;
					Q.push([i, j]);
				}
			}
		}
	}
	return -1;
}

const [HW, ...S] = require("fs").readFileSync("/dev/stdin", "utf8").trim().split('\n');
const [H, W] = HW.split(' ').map(Number)
console.log(bfs(H, W, S));
```
- - -
###### Kotlin
```kotlin
import java.util.*

val D = arrayOf(
	intArrayOf(0, 1), 
	intArrayOf(1, 0), 
	intArrayOf(0, -1), 
	intArrayOf(-1, 0)
)

fun bfs(h: Int, w: Int, s: Array<String>): Int {
	val goal = Array(h) { BooleanArray(w) }
	val cost = Array(h) { IntArray(w) { Int.MAX_VALUE } }
	var y = -1
	var x = -1
	
	for (i in 0 until h) {
		for (j in 0 until w) {
			when (s[i][j]) {
				'A' -> {
					y = i
					x = j
					cost[i][j] = 0
				}
				'B' -> {
					goal[i][j] = true
					for (k in j + 1 until w) {
						if (s[i][k] == '#') break
						goal[i][k] = true
					}
					for (k in i + 1 until h) {
						if (s[k][j] == '#') break
						goal[k][j] = true
					}
					for (k in j - 1 downTo 0) {
						if (s[i][k] == '#') break
						goal[i][k] = true
					}
					for (k in i - 1 downTo 0) {
						if (s[k][j] == '#') break
						goal[k][j] = true
					}
				}
				'#' -> cost[i][j] = -1
			}
		}
	}

	if (goal[y][x]) return cost[y][x]

	val Q: Queue<Pair<Int, Int>> = LinkedList()
	Q.add(Pair(y, x))
	
	while (Q.isNotEmpty()) {
		val (cy, cx) = Q.remove()
		val c = cost[cy][cx] + 1
		
		for (d in D) {
			val i = cy + d[0]
			val j = cx + d[1]
			if (0 <= i && i < h && 0 <= j && j < w) {
				if (goal[i][j]) return c
				if (cost[i][j] > c) {
					cost[i][j] = c
					Q.add(Pair(i, j))
				}
			}
		}
	}
	
	return -1
}

fun main() {
	val sc = Scanner(System.`in`)
	val H = sc.nextInt()
	val W = sc.nextInt()
	val S = Array(H) { sc.next() }
	println(bfs(H, W, S))
	sc.close()
}
```
- - -
###### PHP
```php
<?php
	function bfs($h, $w, $s) {
		$D = [[0, 1], [1, 0], [0, -1], [-1, 0]];
	
		$goal = array_fill(0, $h, array_fill(0, $w, false));
		$cost = array_fill(0, $h, array_fill(0, $w, PHP_INT_MAX));
		
		$y = $x = -1;
	
		for ($i = 0; $i < $h; $i++) {
			for ($j = 0; $j < $w; $j++) {
				if ($s[$i][$j] === 'A') {
					$y = $i;
					$x = $j;
					$cost[$i][$j] = 0;
				} else if ($s[$i][$j] === 'B') {
					$goal[$i][$j] = true;
					for ($k = $j + 1; $k < $w; $k++) {
						if ($s[$i][$k] === '#') break;
						$goal[$i][$k] = true;
					}
					for ($k = $i + 1; $k < $h; $k++) {
						if ($s[$k][$j] === '#') break;
						$goal[$k][$j] = true;
					}
					for ($k = $j - 1; $k >= 0; $k--) {
						if ($s[$i][$k] === '#') break;
						$goal[$i][$k] = true;
					}
					for ($k = $i - 1; $k >= 0; $k--) {
						if ($s[$k][$j] === '#') break;
						$goal[$k][$j] = true;
					}
				} else if ($s[$i][$j] === '#') {
					$cost[$i][$j] = -1;
				}
			}
		}
		
		if ($goal[$y][$x]) return $cost[$y][$x];
	
		$Q = [];
		array_push($Q, [$y, $x]);
	
		while (count($Q) > 0) {
			list($y, $x) = array_shift($Q);
			$c = $cost[$y][$x] + 1;
	
			foreach ($D as $d) {
				$i = $y + $d[0];
				$j = $x + $d[1];
	
				if ($i >= 0 && $i < $h && $j >= 0 && $j < $w) {
					if ($goal[$i][$j]) {
						return $c;
					}
					if ($cost[$i][$j] > $c) {
						$cost[$i][$j] = $c;
						array_push($Q, [$i, $j]);
					}
				}
			}
		}
	
		return -1;
	}
	
	[$H, $W] = array_map('intval', explode(' ', trim(fgets(STDIN))));
	$S = [];
	
	for ($i = 0; $i < $H; $i++) {
		$S[] = trim(fgets(STDIN));
	}
	
	echo bfs($H, $W, $S), PHP_EOL;
?>
```
- - -
###### Perl
```pl
sub bfs {
	my ($h, $w, $s) = @_;
	my @D = ([0, 1], [1, 0], [0, -1], [-1, 0]);
	my @goal = map { [(0) x $w] } (1..$h);
	my @cost = map { [(0x7FFFFFFF) x $w] } (1..$h);
	my ($y, $x);
	for my $i (0..$h-1) {
		for my $j (0..$w-1) {
			if ($s->[$i][$j] eq 'A') {
				$y = $i;
				$x = $j;
				$cost[$i][$j] = 0;
			}
			elsif ($s->[$i][$j] eq 'B') {
				$goal[$i][$j] = 1;
				for (my $k = $j + 1; $k < $w; $k++) {
					last if $s->[$i][$k] eq '#';
					$goal[$i][$k] = 1;
				}
				for (my $k = $i + 1; $k < $h; $k++) {
					last if $s->[$k][$j] eq '#';
					$goal[$k][$j] = 1;
				}
				for (my $k = $j - 1; $k >= 0; $k--) {
					last if $s->[$i][$k] eq '#';
					$goal[$i][$k] = 1;
				}
				for (my $k = $i - 1; $k >= 0; $k--) {
					last if $s->[$k][$j] eq '#';
					$goal[$k][$j] = 1;
				}
			}
			elsif ($s->[$i][$j] eq '#') {
				$cost[$i][$j] = -1;
			}
		}
	}
	return $cost[$y][$x] if $goal[$y][$x];
	my @queue = ([$y, $x]);
	while (my $pos = shift @queue) {
		($y, $x) = @$pos;
		my $c = $cost[$y][$x] + 1;
		
		for my $d (@D) {
			my ($dy, $dx) = @$d;
			my ($i, $j) = ($y + $dy, $x + $dx);
			
			if ($i >= 0 && $i < $h && $j >= 0 && $j < $w) {
				if ($goal[$i][$j]) {
					return $c;
				}
				if ($cost[$i][$j] > $c) {
					$cost[$i][$j] = $c;
					push @queue, [$i, $j];
				}
			}
		}
	}
	return -1;
}

my ($H, $W) = map { int($_) } split ' ', <STDIN>;
my @S;
for (my $i = 0; $i < $H; $i++) {
	chomp(my $s = <STDIN>);
	push @S, [split //, $s];
}
print bfs($H, $W, \@S), "\n";
```
- - -
###### Python3
```py
from queue import Queue

D = ((0, 1), (1, 0), (0, -1), (-1, 0))


def bfs(h, w, s):
	goal = [[False] * w for _ in range(h)]
	cost = [[float('inf')] * w for _ in range(h)]
	y = x = None
	for i in range(h):
		for j in range(w):
			if s[i][j] == 'A':
				y, x = i, j
				cost[i][j] = 0
			elif s[i][j] == 'B':
				goal[i][j] = True
				for k in range(j + 1, w):
					if s[i][k] == '#':
						break
					goal[i][k] = True
				for k in range(i + 1, h):
					if s[k][j] == '#':
						break
					goal[k][j] = True
				for k in range(j - 1, -1, -1):
					if s[i][k] == '#':
						break
					goal[i][k] = True
				for k in range(i - 1, -1, -1):
					if s[k][j] == '#':
						break
					goal[k][j] = True
			elif s[i][j] == '#':
				cost[i][j] = -1
	if goal[y][x]:
		return cost[y][x]
	Q = Queue()
	Q.put((y, x))
	while not Q.empty():
		y, x = Q.get()
		c = cost[y][x] + 1
		for dy, dx in D:
			i, j = y + dy, x + dx
			if 0 <= i < h and 0 <= j < w:
				if goal[i][j]:
					return c
				if cost[i][j] > c:
					cost[i][j] = c
					Q.put((i, j))
	return -1


H, W = map(int, input().split())
print(bfs(H, W, [input() for _ in range(H)]))
```
- - -
###### Ruby
```rb
D = [[0, 1], [1, 0], [0, -1], [-1, 0]]

def bfs(h, w, s)
	goal = Array.new(h) { Array.new(w, false) }
	cost = Array.new(h) { Array.new(w, Float::INFINITY) }
	y, x = nil, nil

	h.times do |i|
		w.times do |j|
			if s[i][j] == 'A'
				y, x = i, j
				cost[i][j] = 0
			elsif s[i][j] == 'B'
				goal[i][j] = true
				(j + 1...w).each do |k|
					break if s[i][k] == '#'
					goal[i][k] = true
				end
				(i + 1...h).each do |k|
					break if s[k][j] == '#'
					goal[k][j] = true
				end
				(j - 1).downto(0).each do |k|
					break if s[i][k] == '#'
					goal[i][k] = true
				end
				(i - 1).downto(0).each do |k|
					break if s[k][j] == '#'
					goal[k][j] = true
				end
			elsif s[i][j] == '#'
				cost[i][j] = -1
			end
		end
	end

	return cost[y][x] if goal[y][x]

	q = Queue.new
	q.push([y, x])

	while !q.empty?
		y, x = q.pop
		c = cost[y][x] + 1
		D.each do |dy, dx|
			i = y + dy
			j = x + dx
			if i >= 0 && i < h && j >= 0 && j < w
				if goal[i][j]
					return c
				end
				if cost[i][j] > c
					cost[i][j] = c
					q.push([i, j])
				end
			end
		end
	end

	return -1
end

H, W = gets.split.map(&:to_i)
S = Array.new(H) { gets.chomp }
puts bfs(H, W, S)
```
- - -
###### Scala
```scala
import scala.collection.mutable._

object Main extends App{

	val D = Array(Array(0, 1), Array(1, 0), Array(0, -1), Array(-1, 0))

	def bfs(h: Int, w: Int, s: Array[String]): Int = {
		val goal = Array.fill(h, w)(false)
		val cost = Array.fill(h, w)(Int.MaxValue)

		var y = -1
		var x = -1

		for (i <- 0 until h) {
			for (j <- 0 until w) {
				s(i).charAt(j) match {
					case 'A' =>
						y = i
						x = j
						cost(i)(j) = 0
					case 'B' =>
						goal(i)(j) = true
						var k = j + 1
						while (k < w && s(i).charAt(k) != '#') {
							goal(i)(k) = true
							k += 1
						}
						k = i + 1
						while (k < h && s(k).charAt(j) != '#') {
							goal(k)(j) = true
							k += 1
						}
						k = j - 1
						while (k >= 0 && s(i).charAt(k) != '#') {
							goal(i)(k) = true
							k -= 1
						}
						k = i - 1
						while (k >= 0 && s(k).charAt(j) != '#') {
							goal(k)(j) = true
							k -= 1
						}
					case '#' =>
						cost(i)(j) = -1
					case _ =>
				}
			}
		}

		if (goal(y)(x)) return cost(y)(x)

		val Q = Queue((y, x))

		while (Q.nonEmpty) {
			val (y, x) = Q.dequeue()
			val c = cost(y)(x) + 1
			for (d <- D) {
				val (i, j) = (y + d(0), x + d(1))
				if (0 <= i && i < h && 0 <= j && j < w) {
					if (goal(i)(j)) return c
					if (cost(i)(j) > c) {
						cost(i)(j) = c
						Q.enqueue((i, j))
					}
				}
			}
		}
		-1
	}

	val sc = new java.util.Scanner(System.in)
	val H = sc.nextInt()
	val W = sc.nextInt()
	val S = Array.fill(H)(sc.next())
	sc.close()
	println(bfs(H, W, S))
}
```
- - -
###### Swift
```swift
let D = [(0, 1), (1, 0), (0, -1), (-1, 0)]

func bfs(h: Int, w: Int, s: [[Character]]) -> Int {
	var goal = Array(repeating: Array(repeating: false, count: w), count: h)
	var cost = Array(repeating: Array(repeating: Int.max, count: w), count: h)
	
	var y: Int? = nil
	var x: Int? = nil
	
	for i in 0..<h {
		for j in 0..<w {
			if s[i][j] == "A" {
				y = i
				x = j
				cost[i][j] = 0
			} else if s[i][j] == "B" {
				goal[i][j] = true
				for k in j+1..<w {
					if s[i][k] == "#" {
						break
					}
					goal[i][k] = true
				}
				for k in i+1..<h {
					if s[k][j] == "#" {
						break
					}
					goal[k][j] = true
				}
				for k in stride(from: j-1, through: 0, by: -1) {
					if s[i][k] == "#" {
						break
					}
					goal[i][k] = true
				}
				for k in stride(from: i-1, through: 0, by: -1) {
					if s[k][j] == "#" {
						break
					}
					goal[k][j] = true
				}
			} else if s[i][j] == "#" {
				cost[i][j] = -1
			}
		}
	}
	
	if let y = y, let x = x, goal[y][x] {
		return Int(cost[y][x])
	}
	
	var queue = [(y!, x!)]
	
	while !queue.isEmpty {
		let (y, x) = queue.removeFirst()
		let c = cost[y][x] + 1
		
		for (dy, dx) in D {
			let i = y + dy
			let j = x + dx
			
			if i >= 0 && i < h && j >= 0 && j < w {
				if goal[i][j] {
					return Int(c)
				}
				if cost[i][j] > c {
					cost[i][j] = c
					queue.append((i, j))
				}
			}
		}
	}
	
	return -1
}

let HW = readLine()!.split(separator: " ").map { Int($0)! }
let H = HW[0]
let W = HW[1]
var S = [[Character]]()

for _ in 0..<H {
	S.append(Array(readLine()!))
}

print(bfs(h: H, w: W, s: S))
```