--->
118 задач
<---
Источники
На шахматной доске расположены несколько слонов и ладей. По условным буквенным обозначениям фигур и их координатам определите, сколько свободных полей шахматной доски не находятся под боем ни одной из этих фигур.
Шахматная доска описывается в восьми строках входных данных. Первые восемь символов каждой из этих строк описывают состояние соответствующей горизонтали: символ B (заглавная латинская буква) означает, что в клетке стоит слон, символ R – ладья, символ * – что клетка пуста.
Выведите количество пустых клеток, которые не бьет ни одна из фигур.
******** ******** *R****** ******** ******** ******** ******** ********
49
Мальчику Васе очень нравится известная игра «Сапер». В нее играет один человек. Игра идет на клетчатом поле размером \(m\)×\(n\) (\(m\) строк, \(n\) столбцов). В некоторых клетках поля стоят мины. В каждой из остальных клеток записано либо число от 1 до 8 – количество мин в соседних с ней клетках, либо ничего не написано – это означает, что в соседних клетках мин нет. Клетки являются соседними, если они имеют хотя бы одну общую вершину. В одной клетке не может стоять более одной мины. Будем называть поле с расположенными на нем минами и числами картой.
Изначально все клетки поля закрыты. Игрок за один ход может открыть какую-нибудь клетку. После этого игроку показывается содержимое этой клетки, и если в открытой им клетке оказывается мина, он проигрывает. В противном случае игра продолжается. Цель игры – открыть все клетки, в которых нет мин.
У Васи на компьютере есть эта игра, но ему кажется, что все карты, которые в ней есть, некрасивые и неинтересные. Поэтому он решил нарисовать свои. При этом он хочет, чтобы карты, которые он нарисует, после того, как они будут открыты, выглядели красиво.
У Васи есть рисунки, нарисованные на клетчатой бумаге следующим образом: некоторые клетки закрашены в черный цвет, а некоторые оставлены белыми. Вася хочет по каждому такому рисунку сделать соответствующее ему поле для игры в «Сапера» по следующему правилу: если на рисунке клетка покрашена в черный цвет, то на этом месте должна быть либо мина, либо число от 1 до 8, если же клетка оставлена белой, то на игровом поле она должна быть пустой.
Напишите программу, которая сделает это за Васю.
В первой строке входного файла содержатся числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 100) – количество строк и столбцов соответственно. Далее идет таблица из \(m\) строк, по \(n\) чисел в каждой строке, задающая Васин рисунок. Каждое число в таблице равно 0 или 1, число 0 означает, что соответствующая клетка на рисунке белая, 1 – черная. Числа в строках разделяются пробелами.
Выходной файл должен содержать \(m\) строк по \(n\) символов – карту игрового поля, \(j\)-ый символ \(i\)-ой строки должен содержать символ «*» (звездочка) если в клетке (\(i\),\(j\)) стоит мина, цифру от 1 до 8, если в этой клетке стоит соответствующее число, либо «.» (точка), если клетка (\(i\),\(j\)) пустая. Символы пробелами не разделяйте. Если построить поле, соответствующее рисунку, невозможно, выходной файл должен содержать одну строку с сообщением «No solution».
3 5 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
***** 23332 .....
3 3 0 1 0 0 0 0 0 0 0
No solution
Недавно один известный художник-абстракционист произвел на свет новый шедевр – картину «Два черных непересекающихся прямоугольника». Картина представляет собой прямоугольник \(m\)×\(n\), разбитый на квадраты 1×1, некоторые из которых закрашены любимым цветом автора – черным. Федя – не любитель абстрактных картин, однако ему стало интересно, действительно ли на картине изображены два непересекающихся прямоугольника. Помогите ему это узнать. Прямоугольники не пересекаются в том смысле, что они не имеют общих клеток.
Первая строка входного файла содержит числа \(m\) и \(n\) (1 ≤ \(m\), \(n\) ≤ 200). Следующие \(m\) строк содержат описание рисунка. Каждая строка содержит ровно \(n\) символов. Символ «.» обозначает пустой квадрат, а символ «#» – закрашенный.
Если рисунок можно представить как два непересекающихся прямоугольника, выведите в первой строке «YES», а в следующих m строках выведите рисунок в том же виде, в каком он задан во входном файле, заменив квадраты, соответствующие первому прямоугольнику на символ «a», а второму – на символ «b». Если решений несколько, выведите любое.
Если же этого сделать нельзя, выведите в выходной файл «NO».
2 1 # .
NO
2 2 .. ##
YES .. ab
1 3 ###
YES abb
3 1 . # #
YES . a b
Енот Вася — начинающий художник. Недавно он приобрёл подержанную кисточку (как рассказал продавец, она сделана из хвоста самого Малевича!), достал холст и решил произвести на свет свой первый шедевр.
Как оказалось, лет кисточке немало, потому она способна лишь ставить кляксы в форме пяти квадратиков, расположенных крестиком (координаты их центров будут равны (\(x\), \(y\)), (\(x\)−1, \(y\)), (\(x\), \(y\)−1), (\(x\)+1, \(y\)), (\(x\), \(y\)+1)). Вася поставил \(N\) клякс, разочаровался в идее первого шедевра и задумался о месте для нового. Но ведь если он закрасил весь холст, писать будет негде...
Выясните, закрасил ли своими действиями Вася весь холст.
Первая строка входного файла содержит три целых числа \(W\), \(H\) и \(N\) — ширину и высоту холста в квадратиках (1 \(\le\) \(W\), \(H\) \(\le\) \(10^9\)) и количество клякс, поставленных Васей (0 \(\le\) \(N\) \(\le\) \(10^6\)). Следующие \(N\) строк содержат по два целых числа \(x_i\), \(y_i\) каждая — координаты среднего квадратика \(i\)-й кляксы (−\(10^9\) \(\le\) \(x_i\), \(y_i\) \(\le\) \(10^9\)). Клетка (\(x\), \(y\)) находится на холсте, если 1 \(\le\) \(x\) \(\le\) \(W\) и 1 \(\le\) \(y\) \(\le\) \(H\). Части клякс, оказавшиеся вне холста, не учитываются.
Выведите «Yes», если Вася закрасил весь холст, и «No» в противном случае.
Миша уже научился хорошо фотографировать и недавно увлекся программированием. Первая программа, которую он написал, позволяет формировать негатив чёрно-белого изображения.
Бинарное чёрно-белое изображение — это прямоугольник, состоящий из пикселей, каждый из которых может быть либо чёрным, либо белым. Негатив такого изображения получается путём замены каждого чёрного пикселя на белый, а каждого белого пикселя — на чёрный.
Миша, как начинающий программист, написал свою программу с ошибкой, поэтому в результате её исполнения мог получаться некорректный негатив. Для того чтобы оценить уровень несоответствия получаемого негатива исходному изображению, Миша начал тестировать свою программу.
В качестве входных данных он использовал исходные изображения. Сформированные программой негативы он начал тщательно анализировать, каждый раз определяя число пикселей негатива, которые получены с ошибкой.
Требуется написать программу, которая в качестве входных данных использует исходное бинарное чёрно-белое изображение и полученный Мишиной программой негатив, и на основе этого определяет количество пикселей, в которых допущена ошибка.
Первая строка входного файла содержит целые числа \(n\) и \(m\) (\(1\le n,m\le100\)) — высоту и ширину исходного изображения (в пикселях).
Последующие \(n\) строк содержат описание исходного изображения. Каждая строка состоит из \(m\) символов «B» и «W». Символ «B» соответствует чёрному пикселю, а символ «W» — белому.
Далее следует пустая строка, а после неё — описание выведенного Мишиной программой изображения в том же формате, что и исходное изображение.
В выходной файл необходимо вывести число пикселей негатива, которые неправильно сформированы Мишиной программой.
3 4 WBBW BBBB WBBW BWWW WWWB BWWB
2
2 2 BW BB WW BW
2