Lösen mit Ruby, Python und numpy AtCoder ABC054 B Matrixberechnung

Einführung

• AtCoder-Probleme * Verwendet Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

AtCoder Beginner Contest B - Template Matching Difficulty: 828

Dieses Thema, Matrixberechnung

Es ist ein zweidimensionales Array, aber die Verwendung einer Matrizenbibliothek kann Operationen einfacher machen. Ruby

ruby.rb

require 'matrix'

class Matrix
  # v2.Kann nicht in 3 zugewiesen werden
  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.Kann nicht in 3 zugewiesen werden
  def []=(i, j, x)
    @rows[i][j]=x
  end
end

Rufen Sie die Matrixbibliothek mit "require'matrix" auf. In der lokalen Umgebung "v2.7.1" kann es den Elementen der Matrix zugewiesen werden, in der AtCoder-Umgebung "v2.3.3" kann es jedoch nicht zugewiesen werden, sodass eine Methode hinzugefügt wird. Das Interessante an ** Ruby ** ist, dass Sie dies auch für Standardbibliotheken tun können.

minor.rb

    if a.minor(i, m, j, m) == b

Die Submatrix wird von "minor" erfasst und die Matrix wird verglichen.

error.rb

(n - m).times do |i|
  (n - m).times do |j|

(n - m + 1).times do |i|
  (n - m + 1).times do |j|

Im Fall einer ~~ 1 x 1 Matrix läuft der Matrixvergleich nicht gut, so dass die entsprechende Verarbeitung enthalten ist. ~~ (n - m) war falsch und (n - m + 1) war richtig.

** Nachtrag ** Die zweidimensionale Array-Version finden Sie im Kommentarbereich. 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):

Der Vergleich der Numpy-Matrix gibt beispielsweise "[[True, True], [True, True]]" zurück. Daher verwenden wir die Funktion "all", um zu überprüfen, ob alle "True" sind.

Zusammenfassung

• Gelöstes ABC 054 B.
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Python vertraut
• Wurde mit Numpy vertraut