Ruby と Perl と Java と Python で解く AtCoder AGC 033 A 幅優先探索

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
# 今回のお題
*[AtCoder Grand Contest 033 A - Darker and Darker](https://atcoder.jp/contests/agc033/tasks/agc033_a)*
<font color="light blue">Difficulty: 1245</font>

今回のテーマ、幅優先探索
# Ruby
以前解きました *[AtCoder Typical Contest 002 A - 幅優先探索](https://atcoder.jp/contests/atc002/tasks/abc007_3)* の応用編になります。
特に、`実行時間制限: 1 sec` と厳しい条件が付いています。

```ruby.rb
h, w = gets.split.map(&:to_i)
cm = Array.new(h + 2){Array.new(w + 2, 0)}
que = []
1.upto(h) do |i|
  s = gets.chomp
  1.upto(w) do |j|
    if s[j - 1] == '.'
      cm[i][j] = -1
    else
      que.push(i)
      que.push(j)
    end
  end
end
ans = 0
while que.size > 0
  y = que.shift
  x = que.shift
  ans = cm[y][x] + 1
  if cm[y + 1][x] == -1
    cm[y + 1][x] = ans
    que.push(y + 1)
    que.push(x)
  end
  if cm[y - 1][x] == -1
    cm[y - 1][x] = ans
    que.push(y - 1)
    que.push(x)
  end
  if cm[y][x + 1] == -1
    cm[y][x + 1] = ans
    que.push(y)
    que.push(x + 1)
  end
  if cm[y][x - 1] == -1
    cm[y][x - 1] = ans
    que.push(y)
    que.push(x - 1)
  end
end
puts ans - 1
```
*[前回のコード](https://qiita.com/superrino130/items/7f314086fc6ea01af410)* をコピペし、若干の修正を加えるだけで<font color="light blue">水diff</font>クリア。

```array.rb
cm = Array.new(h + 2){Array.new(w + 2, 0)}
```
上下左右をチェックする際、`nil`でエラーを貰わない様、配列を大きくしています。

```push.rb
h, w = gets.split.map(&:to_i)
cm = Array.new(h + 2){Array.new(w + 2, 0)}
que = []
1.upto(h) do |i|
  s = gets.chomp
  1.upto(w) do |j|
    if s[j - 1] == '.'
      cm[i][j] = -1
    else
      que << i << j
      cm[i][j] = 0
    end
  end
end
ans = 0
while que.size > 0
  y = que.shift
  x = que.shift
  ans = cm[y][x] + 1
  if cm[y + 1][x] == -1
    cm[y + 1][x] = ans
    que << y + 1 << x
  end
  if cm[y - 1][x] == -1
    cm[y - 1][x] = ans
    que << y - 1 << x
  end
  if cm[y][x + 1] == -1
    cm[y][x + 1] = ans
    que << y << x + 1
  end
  if cm[y][x - 1] == -1
    cm[y][x - 1] = ans
    que << y << x - 1
  end
end
puts ans - 1
```
コメントでいただいた`push`の代わりに`<<`を使用するコードです。
こちらは、実行時間が短縮しています。
# Python
*Python* は今回`TLE` でした。
他の競技者の解答を見てみると、`numpy` を使用している例が多いです。

```cmd.exe
C:\Users\user>pacman -S mingw-w64-x86_64-python-numpy
```
早速インストールしました。

**追記**
PyPyですと通りました。

```PyPy.py
from collections import deque

h, w = map(int, input().split())
cm = [[0 for j in range(w + 2)] for i in range(h + 2)]
que = deque([])
for i in range(1, h + 1):
    s = input()
    for j in range(1, w + 1):
        if s[j - 1] == ".":
            cm[i][j] = -1
        else:
            que.append(i)
            que.append(j)
ans = 0
while len(que) > 0:
    y = que.popleft()
    x = que.popleft()
    ans = cm[y][x] + 1
    if cm[y + 1][x] == -1:
        cm[y + 1][x] = ans
        que.append(y + 1)
        que.append(x)
    if cm[y - 1][x] == -1:
        cm[y - 1][x] = ans
        que.append(y - 1)
        que.append(x)
    if cm[y][x + 1] == -1:
        cm[y][x + 1] = ans
        que.append(y)
        que.append(x + 1)
    if cm[y][x - 1] == -1:
        cm[y][x - 1] = ans
        que.append(y)
        que.append(x - 1)
print(ans - 1)
```
# Perl
*Perl* は今回`TLE` でした。
他の競技者の解答を見てみると．．．せっ 正解者が誰もいない。

# Java
今回は２本立てです。
一つ目は、*[前回のコード](https://qiita.com/superrino130/items/7f314086fc6ea01af410)* をコピペして、若干の修正を加えたもの。

```java.java
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        int cm[][] = new int[h + 2][w + 2];
        Deque<Integer> que = new ArrayDeque<>();
        for (int i = 1; i <= h; i++) {
            String s = sc.next();
            for (int j = 1; j <= w; j++) {
                if (".".equals(s.substring(j - 1, j))) {
                    cm[i][j] = -1;
                } else {
                    que.add(i);
                    que.add(j);
                }
            }
        }
        sc.close();
        int ans = 0;
        while (que.size() > 0) {
            int y = que.poll();
            int x = que.poll();
            ans = cm[y][x] + 1;
            if (cm[y + 1][x] == -1) {
                cm[y + 1][x] = ans;
                que.add(y + 1);
                que.add(x);
            }
            if (cm[y - 1][x] == -1) {
                cm[y - 1][x] = ans;
                que.add(y - 1);
                que.add(x);
            }
            if (cm[y][x + 1] == -1) {
                cm[y][x + 1] = ans;
                que.add(y);
                que.add(x + 1);
            }
            if (cm[y][x - 1] == -1) {
                cm[y][x - 1] = ans;
                que.add(y);
                que.add(x - 1);
            }
        }
        System.out.println(ans - 1);
    }
}
```
```array.java
        int cm[][] = new int[h + 2][w + 2];
```
上下左右をチェックする際、`ArrayIndexOutOfBoundsException`を貰わない様、配列を大きくしています。

```class.java
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        int s[][] = new int[h + 2][w + 2];
        Queue<Pair> que = new ArrayDeque<>();
        for (int i = 1; i <= h; i++) {
            char c[] = sc.next().toCharArray();
            for (int j = 1; j <= w; j++) {
                if (c[j - 1] == '.') {
                    s[i][j] = -1;
                } else {
                    que.add(new Pair(i, j));
                }

            }
        }
        sc.close();

        Pair p;
        int ans = 0;
        while (!que.isEmpty()) {
            p = que.poll();
            ans = s[p.x][p.y] + 1;
            if (s[p.x + 1][p.y] == -1) {
                s[p.x + 1][p.y] = ans;
                que.add(new Pair(p.x + 1, p.y));
            }
            if (s[p.x - 1][p.y] == -1) {
                s[p.x - 1][p.y] = ans;
                que.add(new Pair(p.x - 1, p.y));
            }
            if (s[p.x][p.y + 1] == -1) {
                s[p.x][p.y + 1] = ans;
                que.add(new Pair(p.x, p.y + 1));
            }
            if (s[p.x][p.y - 1] == -1) {
                s[p.x][p.y - 1] = ans;
                que.add(new Pair(p.x, p.y - 1));
            }
        }
        System.out.println(ans - 1);
    }
}

class Pair {
    int x;
    int y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
```
ArrayDeque が遅い様なので、出し入れを減らすためクラスを生成しクラスごと渡しています。

*Java* は、やればできる子でした。

||Ruby|Ruby(<<)|Python|PyPy|Perl|Java|Java(class)|
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
|コード長 (Byte)|753|676|878|878|777|1511|1580|
|実行時間 (ms)|843|801|<font color="orange">TLE</font>|599 |<font color="orange">TLE</font>|779|345|
|メモリ (KB)|27132|27132|52484|37692|174720|114932|70740|
# まとめ
+ AGC 033 A を解いた
+ Ruby に詳しくなった
+ numpy をインストールした
+ Java はできる子でした

参照したサイト
*[numpyの使い方](https://qiita.com/jyori112/items/a15658d1dd17c421e1e2)*
*[Ruby と Perl と Java と Python で解く AtCoder ATC 002 A](https://qiita.com/superrino130/items/7f314086fc6ea01af410)*