AtCoder Beginner Contest B - Template Matching Difficulty: 828
This theme, matrix operation
It's a two-dimensional array, but using a matrix library can make operations easier. Ruby
ruby.rb
require 'matrix'
class Matrix
# v2.Cannot be assigned in 3
def []=(i, j, x)
@rows[i][j]=x
end
end
n, m = gets.split.map(&:to_i)
rows = Array.new(n + m){gets.chomp.chars.map{|c| (c == '#') ? 1 : 0}}
a = Matrix.rows(rows.shift(n))
b = Matrix.rows(rows)
(n - m + 1).times do |i|
(n - m + 1).times do |j|
if a.minor(i, m, j, m) == b
puts "Yes"
exit
end
end
end
puts "No"
matrix.rb
require 'matrix'
class Matrix
# v2.Cannot be assigned in 3
def []=(i, j, x)
@rows[i][j]=x
end
end
Call the matrix library with require'matrix'.
In the local environment v2.7.1, it can be assigned to the matrix element, but in the AtCoder environment v2.3.3, it cannot be assigned, so a method is added.
The interesting thing about ** Ruby ** is that you can do this for the standard library as well.
minor.rb
if a.minor(i, m, j, m) == b
Submatrix is acquired by minor and matrix comparison is performed.
error.rb
(n - m).times do |i|
(n - m).times do |j|
(n - m + 1).times do |i|
(n - m + 1).times do |j|
When the matrix is ~~ 1 x 1, the matrix comparison does not go well, so the corresponding processing is included. ~~ (n --m) was wrong and (n --m + 1) was correct.
** Addition ** Please refer to the comment section for the 2D array version. Python
import numpy
n, m = map(int, input().split())
a = numpy.zeros([n, n], dtype=int)
b = numpy.zeros([m, m], dtype=int)
for i in range(n):
s = input()
for j in range(n):
if s[j] == '#':
a[i, j] = 1
for i in range(m):
s = input()
for j in range(m):
if s[j] == '#':
b[i, j] = 1
for i in range(n - m + 1):
for j in range(n - m + 1):
if numpy.all(a[i: i + m, j: j + m] == b):
print("Yes")
exit()
print("No")
all.py
if numpy.all(a[i: i + m, j: j + m] == b):
Numpy matrix comparison returns, for example, [[True, True], [True, True]], so I'm using the all function to check if everything is True.
| Ruby (Matrix) | Ruby (Array) | Python (numpy) | |
|---|---|---|---|
| Code length(Byte) | 420 | 288 | 534 |
| Execution time(ms) | 22 | 10 | 166 |
| memory(KB) | 3196 | 1788 | 12512 |
Recommended Posts