Ruby と Perl と Java と Python で解く AtCoder ATC 002 A

# はじめに
AtCoder Typical Contest(ATC) とは、競技プログラミングにおける、典型問題を出題するコンテストです。
AtCoder さん、ありがとうございます。
# 今回のお題
*[AtCoder Typical Contest 002 A - 幅優先探索](https://atcoder.jp/contests/atc002/tasks/abc007_3)*

今回のテーマ、幅優先探索
# Ruby
DFS(深さ優先探索)とBFS(幅優先探索)の違いについて、いろいろあると思いますが、ここではデータの流れに注目します。

||DFS|BFS|
|:--:|:--:|:--:|
||後入れ先出し|先入れ先出し|
|データ構造|スタック|キュー|
|データを入れる|push|push|
|データを取り出す|pop|shift|

```ruby.rb
r, c = gets.split.map(&:to_i)
sy, sx = gets.split.map(&:to_i)
gy, gx = gets.split.map(&:to_i)
cm = Array.new(r + 1).map{Array.new(c + 1, 0)}
1.upto(r) do |i|
  s = gets.chomp
  1.upto(c) do |j|
    cm[i][j] = -1 if s[j - 1] == '.'
  end
end
que = []
que.push(sy)
que.push(sx)
cm[sy][sx] = 0
while que.size > 0
  y = que.shift
  x = que.shift
  if cm[y + 1][x] == -1
    cm[y + 1][x] = cm[y][x] + 1
    que.push(y + 1)
    que.push(x)
  end
  if cm[y - 1][x] == -1
    cm[y - 1][x] = cm[y][x] + 1
    que.push(y - 1)
    que.push(x)
  end
  if cm[y][x + 1] == -1
    cm[y][x + 1] = cm[y][x] + 1
    que.push(y)
    que.push(x + 1)
  end
  if cm[y][x - 1] == -1
    cm[y][x - 1] = cm[y][x] + 1
    que.push(y)
    que.push(x - 1)
  end
end
puts cm[gy][gx]
```
que に push して shift して que が空になるまで while で回す要領です。

|末尾にデータを追加|先頭のデータを取り出す
|:--:|:--:|
|push|shift|
```que.rb
que.push(sy)
que.push(sx)
```
xy 座標を別々に push していますが、~~リファレンスで配列ごと渡してもいいと思います。~~`<<` を使用した方が速い様です。
*[Ruby と Perl と Java と Python で解く AtCoder AGC 033 A 幅優先探索](https://qiita.com/superrino130/items/5d3059a100e23bcbbe37#comment-5ea8271cc49b6c555858)*

```array.rb
  if cm[y + 1][x] == -1
  if cm[y - 1][x] == -1
  if cm[y][x + 1] == -1
  if cm[y][x - 1] == -1
```
上下左右をチェックしていますが、出題によっては右と下のみに減ったりします。
# Python
```python.py
from collections import deque

r, c = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
cm = [[0 for j in range(c + 1)] for i in range(r + 1)]
for i in range(1, r + 1):
    s = input()
    for j in range(1, c + 1):
        if s[j - 1] == ".":
            cm[i][j] = -1
que = deque([])
que.append(sy)
que.append(sx)
cm[sy][sx] = 0
while len(que) > 0:
    y = que.popleft()
    x = que.popleft()
    if cm[y + 1][x] == -1:
        cm[y + 1][x] = cm[y][x] + 1
        que.append(y + 1)
        que.append(x)
    if cm[y - 1][x] == -1:
        cm[y - 1][x] = cm[y][x] + 1
        que.append(y - 1)
        que.append(x)
    if cm[y][x + 1] == -1:
        cm[y][x + 1] = cm[y][x] + 1
        que.append(y)
        que.append(x + 1)
    if cm[y][x - 1] == -1:
        cm[y][x - 1] = cm[y][x] + 1
        que.append(y)
        que.append(x - 1)
print(cm[gy][gx])
```
deque の場合

|末尾にデータを追加|先頭のデータを取り出す
|:--:|:--:|
|append|popleft|
# Perl
```perl.pl
chomp (my ($r, $c) = split / /, <STDIN>);
chomp (my ($sy, $sx) = split / /, <STDIN>);
chomp (my ($gy, $gx) = split / /, <STDIN>);
my @cm;
for my $i (1..$r) {
  chomp (my $s = <STDIN>);
  for my $j (1..$c) {
    $cm[$i][$j] = -1 if substr($s, $j - 1, 1) eq '.';
  }
}
my @que;
push @que, $sy;
push @que, $sx;
$cm[$sy][$sx] = 0;
while(@que) {
  my $y = shift @que;
  my $x = shift @que;
  if ($cm[$y + 1][$x] == -1) {
    $cm[$y + 1][$x] = $cm[$y][$x] + 1;
    push @que, $y + 1;
    push @que, $x;
  }
  if ($cm[$y - 1][$x] == -1) {
    $cm[$y - 1][$x] = $cm[$y][$x] + 1;
    push @que, $y - 1;
    push @que, $x;
  }
  if ($cm[$y][$x + 1] == -1) {
    $cm[$y][$x + 1] = $cm[$y][$x] + 1;
    push @que, $y;
    push @que, $x + 1;
  }
  if ($cm[$y][$x - 1] == -1) {
    $cm[$y][$x - 1] = $cm[$y][$x] + 1;
    push @que, $y;
    push @que, $x - 1;
  }
}
print $cm[$gy][$gx], "\n";
```
|末尾にデータを追加|先頭のデータを取り出す
|:--:|:--:|
|push|shift|
# Java
```java.java
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int r = Integer.parseInt(sc.next());
        int c = Integer.parseInt(sc.next());
        int sy = Integer.parseInt(sc.next());
        int sx = Integer.parseInt(sc.next());
        int gy = Integer.parseInt(sc.next());
        int gx = Integer.parseInt(sc.next());
        int cm[][] = new int[r + 1][c + 1];
        for (int i = 1; i <= r; i++) {
            String s = sc.next();
            for (int j = 1; j <= c; j++) {
                if (".".equals(s.substring(j - 1, j))) {
                    cm[i][j] = -1;
                }
            }
        }
        sc.close();
        Deque<Integer> que = new ArrayDeque<>();
        que.add(sy);
        que.add(sx);
        cm[sy][sx] = 0;
        while (que.size() > 0) {
            int y = que.poll();
            int x = que.poll();
            if (cm[y + 1][x] == -1) {
                cm[y + 1][x] = cm[y][x] + 1;
                que.add(y + 1);
                que.add(x);
            }
            if (cm[y - 1][x] == -1) {
                cm[y - 1][x] = cm[y][x] + 1;
                que.add(y - 1);
                que.add(x);
            }
            if (cm[y][x + 1] == -1) {
                cm[y][x + 1] = cm[y][x] + 1;
                que.add(y);
                que.add(x + 1);
            }
            if (cm[y][x - 1] == -1) {
                cm[y][x - 1] = cm[y][x] + 1;
                que.add(y);
                que.add(x - 1);
            }
        }
        System.out.println(cm[gy][gx]);
    }
}
```
Deque の場合

|末尾にデータを追加|先頭のデータを取り出す
|:--:|:--:|
|add|poll|

||Ruby|Python|Perl|Java|
|:--:|:--:|:--:|:--:|:--:|
|コード長|791 Byte|935 Byte|915 Byte|1660 Byte|
|実行時間|10 ms|24 ms|5 ms|106 ms|
|メモリ|1788 KB|3436 KB|512 KB|23636 KB|
# まとめ
+ ATC 002 A を解いた
+ Ruby に詳しくなった
+ Python に詳しくなった
+ Perl に詳しくなった
+ Java に詳しくなった

参照したサイト
*[Pythonのスタックとキューには何を使えばいいのか（各データ構造の速度比較）](https://qiita.com/saba/items/107c4237206e31acdbef)*