Табло

ЗАДАЧА №446

Табло

(Время: 1 сек. Память: 16 Мб Сложность: 20%)

На хоккейном стадионе в одном большом городе расположено большое прямоугольное табло. Оно имеет n строк и m столбцов (то есть состоит из n x m ячеек). Во время хоккейного матча это табло служит для отображения счета и времени, прошедшего с начала тайма, а в перерывах на нем показывают различную рекламу.

В связи с этим возникла задача проверки возможности показа на этом табло определенной рекламной заставки. Заставка, также как и табло, имеет размер n строк на m столбцов. Каждая из ячеек заставки окрашена в один из четырех цветов — трех основных: красный — R, зеленый — G, синий — B и черный — .(точка).

Каждая из ячеек табло характеризуется своими цвето-передаточными возможностями. Любая из ячеек табло может отображать черный цвет — это соответствует тому, что на нее вообще не подается напряжение. Также каждая из ячеек может отображать некоторое подмножество множества основных цветов. В этой задаче эти подмножества будут кодироваться следующим образом:

  • 0 — ячейка может отображать только черный цвет;
  • 1 — ячейка может отображать только черный и синий цвета;
  • 2 — ячейка может отображать только черный и зеленый цвета;
  • 3 — ячейка может отображать только черный, зеленый и синий цвета;
  • 4 — ячейка может отображать только черный и красный цвета;
  • 5 — ячейка может отображать только черный, красный и синий цвета;
  • 6 — ячейка может отображать только черный, красный и зеленый цвета;
  • 7 — ячейка может отображать только черный, красный, зеленый и синий цвета.

Напишите программу, которая по описанию табло и заставки определяет: возможно ли на табло отобразить эту заставку.

Входные данные

Первая строка входного файла INPUT.TXT содержит целые числа n и m (1 <= n, m <= 100). Далее идут n строк по m символов каждая — описание заставки. Каждый из символов описания заставки принадлежит множеству {R, G, B, .} . Их значения описаны выше.

После этого идет описание табло. Оно содержит n строк по m чисел, разделенных пробелами. Значения чисел описаны выше.

Выходные данные

В выходной файл OUTPUT.TXT выведите YES, если на табло возможно отобразить заставку и NO — в противном случае.

Примеры

INPUT.TXT      OUTPUT.TXT

3   3
.GB
R.B
RG.
0   1   2
3   4   5
6   7   0                             NO

 

2   3
RGB
.G.
7   7   7
7   7   7                              YES

 

Идея решения

Несмотря на сложную формулировку и наибольшую длину кода, требуемого для решения задачи, указанная на сайте сложность задачи минимальна.

Технически для решения задачи требуется умение работать с двумерными массивами. Необходимо уметь считать из файла (консоли) заданную информацию и сформировать два двумерных массива tablo и zastavka одинакового размера n * m. Необходимо также сформировать одномерный массив code из 8 ячеек, элементы которого задают строку, содержащую цвета, допустимые для данного кода. Например, code[0] = “P”, а code[7] = “PRGB”. Это означает, что нулевой код допускает изображение только черного цвета, заданного буквой “P”, а код, заданный цифрой 7, допускает как черный, так и все остальные цвета.

Массив zastavka может быть символьного или строкового типа. Его элемент — zastavka [i, j] задает цвет, который должен быть отображен на табло.

Массив tablo имеет целочисленный тип. Его элемент — tablo [i, j] задает код, определяющий цвета, которые могут быть отображены этим элементом табло. Так, если tablo [i, j] равно 7, то этот элемент табло может отобразить любой цвет, заданный соответствующим элементом заставки.

Если описание массивов и их инициализация выполнены корректно, то дальнейшая обработка проста. В цикле по числу строк и числу столбцов проверяется, может ли соответствующий элемент табло отобразить требуемый цвет заставки. Технически эта проверка сводится к тому, что код элемента табло содержит символ, заданный элементом заставки. Если хотя бы для одного элемента табло проверка не заканчивается успехом, то выдается результат «NO». Результат «YES» выдается в случае, когда проверка заканчивается успехом для всех элементов табло.

Вот как выглядит программа на C#, решающая эту задачу:

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

 

namespace Tablo

{

class Program

{

static void Main(string[] args)

{

int n, m;

Console.WriteLine(«Введите число строк табло»);

n = int.Parse(Console.ReadLine());

Console.WriteLine(«Введите число столбцов табло»);

m = int.Parse(Console.ReadLine());

string[,] zastavka = new string [n,m];

string zastavka_line;

string[] z_line = new string[m];

for (int i = 0; i < n; i++)

{

Console.WriteLine(

«Введите элементы строки заставки, разделенные пробелом»);

zastavka_line = Console.ReadLine();

z_line = zastavka_line.Split(‘ ‘);

for (int j = 0; j < m; j++)

zastavka[i, j] = z_line[j];

}

int[,] tablo = new int [n,m];

string tablo_line;

string[] t_line = new string[m];

for(int i = 0; i < n; i++ )

{

Console.WriteLine(

«Введите элементы строки табло, разделенные пробелом»);

tablo_line = Console.ReadLine();

t_line = tablo_line.Split(‘ ‘);

for (int j = 0; j < m; j++)

tablo[i, j] = int.Parse(t_line[j]);

}

 

string[] code = new string[8];

code[0] = «P»; code[1] = «PB»; code[2] = «PG»; code[3] = «PGB»;

code[4] = «PR»; code[5] = «PBR»;

code[6] = «PGR»; code[7] = «PGBR»;

bool show = true;

int item_tablo = 0;

int k = 0;

while(show && k < n)

{

int j = 0;

while (show && j < m)

{

item_tablo = tablo[k, j];

if (code[item_tablo].IndexOf(zastavka[k, j]) < 0)

show = false;

j++;

}

k++;

}

if (show)

Console.WriteLine(«YES»);

else

Console.WriteLine(«NO»);

}

}

}