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

はじめに

AtCoder Typical Contest(ATC) とは、競技プログラミングにおける、典型問題を出題するコンテストです。
AtCoder さん、ありがとうございます。

今回のお題

AtCoder Typical Contest 002 A - 幅優先探索

今回のテーマ、幅優先探索

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 幅優先探索

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のスタックとキューには何を使えばいいのか（各データ構造の速度比較）