Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A

Introduction

AtCoder Typical Contest (ATC) is a contest that asks typical questions in competitive programming. Thank you, AtCoder.

This theme

• AtCoder Typical Contest 002 A --Breadth-first search *

This theme, breadth-first search Ruby I think there are various differences between DFS (depth-first search) and BFS (breadth-first search), but here we will focus on the data flow.

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]

Push to que, shift, and turn while while until que is empty.

que.rb

que.push(sy)
que.push(sx)

I'm pushing the xy coordinates separately, but I think you can pass the entire array in the ~~ reference. It seems faster to use ~~ <<.

• Solving with Ruby, Perl, Java and Python AtCoder AGC 033 A breadth-first search *

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

I check up, down, left and right, but depending on the question, it may be reduced to right and bottom only. 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])

For deque

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";

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]);
    }
}

For Deque

Summary

• Solved ATC 002 A
• Become familiar with Ruby
• Become familiar with Python
• Become familiar with Perl
• Become familiar with Java

Referenced site

• What to use for Python stacks and queues (speed comparison of each data structure) *