LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

プログラミングゲームの解答コードを投稿しよう！
@anonymously115

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

Posted at

paizaの新作プログラミングゲーム【電脳少女プログラミング2088 ─壊レタ君を再構築─】新都心のハイウェイ（paizaランク：A相当）をやってみました。

問題

方針

幅優先探索を使います。
ゴールとして、「Bの上下左右方向の壁マスに当たるまでの全てのマス」を設定します。
highway.png

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++
#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#
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
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
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
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
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
	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
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
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
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
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
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))
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?