はじめに
AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
今回のお題
AtCoder Grand Contest 033 A - Darker and Darker
Difficulty: 1245
今回のテーマ、幅優先探索
Ruby
以前解きました AtCoder Typical Contest 002 A - 幅優先探索 の応用編になります。
特に、実行時間制限: 1 sec
と厳しい条件が付いています。
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
前回のコード をコピペし、若干の修正を加えるだけで水diffクリア。
cm = Array.new(h + 2){Array.new(w + 2, 0)}
上下左右をチェックする際、nil
でエラーを貰わない様、配列を大きくしています。
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
を使用している例が多いです。
C:\Users\user>pacman -S mingw-w64-x86_64-python-numpy
早速インストールしました。
追記
PyPyですと通りました。
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
今回は2本立てです。
一つ目は、前回のコード をコピペして、若干の修正を加えたもの。
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);
}
}
int cm[][] = new int[h + 2][w + 2];
上下左右をチェックする際、ArrayIndexOutOfBoundsException
を貰わない様、配列を大きくしています。
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 | TLE | 599 | TLE | 779 | 345 |
メモリ (KB) | 27132 | 27132 | 52484 | 37692 | 174720 | 114932 | 70740 |
まとめ
- AGC 033 A を解いた
- Ruby に詳しくなった
- numpy をインストールした
- Java はできる子でした
参照したサイト
numpyの使い方
Ruby と Perl と Java と Python で解く AtCoder ATC 002 A