Résolution avec Ruby, Perl, Java et Python AtCoder ATC 002 A

introduction

Le concours typique AtCoder (ATC) est un concours qui pose des questions typiques dans la programmation compétitive. Merci, AtCoder.

Ce thème

• Concours typique AtCoder 002 A - Recherche de priorité large *

Ce thème, recherche de priorité de largeur Ruby Je pense qu'il existe diverses différences entre DFS (recherche de priorité de profondeur) et BFS (recherche de priorité de largeur), mais nous nous concentrerons ici sur le flux de données.

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]

Poussez pour que, changez et tournez pendant que jusqu'à ce que que soit vide.

que.rb

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

Je pousse les coordonnées xy séparément, mais je pense que vous pouvez passer le tableau entier dans la référence ~~. Il semble plus rapide d'utiliser ~~ <<.

• Résolution avec Ruby, Perl, Java et Python AtCoder AGC 033 A Width Priority 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

Je vérifie en haut, en bas, à gauche et à droite, mais selon la question, il peut être réduit à droite et en bas uniquement. 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])

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

Pour Deque

Résumé

• Résolu ATC 002 A
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python
• Familiarisez-vous avec Perl
• Familiarisez-vous avec Java

Site référencé

• Quoi utiliser pour les piles et les files d'attente Python (comparaison de vitesse de chaque structure de données) *