Задача
Петя очень любит шоколад. И Маша очень любит шоколад. Недавно Петя купил шоколадку и теперь хочет поделиться ею с Машей. Шоколадка представляет собой прямоугольник $n \cdot m$, который полностью состоит из маленькихшоколадных долек — прямоугольников $2 \cdot 1$. 
Петя делит шоколадку на две части, разламывая ее вдоль некоторой прямой, параллельной одному из краев шоколадки. Ни Петя, ни Маша не любят ломаные дольки, поэтому Петя хочет разломать шоколадку так, чтобы ни одна долька не была повреждена.
Помогите Пете поделиться шоколадкой с Машей.
Входные данные
В первой строке входного файла два целых числа $n$ и $m$ ($1 \le n, m \le 20$, хотя бы одно из чисел $n$ и $m$ — четно). Далее следуют $n$ строк по $m$ чисел в каждой — номера долек, в которые входят соответствующие кусочки шоколадки. Дольки имеют номера от $1$ до $\frac{n \cdot m}{2}$, и никакие две дольки не имеют одинаковые номера.
Выходные данные
В выходной файл выведите «$Yes$», если Петя может разломать шоколадку, не повредив дольки. Иначе выведите «$No$».
TESTS
| Входные данные | Выходные данные |
|---|---|
| 2 3 1 1 2 3 3 2 |
Yes |
| 5 6 1 2 2 3 3 4 1 5 6 7 7 4 8 5 6 9 10 10 8 11 11 9 12 13 14 14 15 15 12 13 |
No |
| 4 7 1 1 2 5 8 11 6 2 14 4 7 3 9 5 3 7 10 6 13 2 3 4 3 8 12 5 7 7 |
Yes |
Код решения
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
import java.io.InputStream; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.Scanner; public class Main { public static void main(String[] args) { new Resolver(System.in, System.out).solve(); } public static class Resolver { private Scanner scanner; private PrintWriter writer; public Resolver(InputStream is, OutputStream os) { this.scanner = new Scanner(is); this.writer = new PrintWriter(os); } public void solve() { int rowCount = scanner.nextInt(); int columnCount = scanner.nextInt(); int[][] chocolate = new int[rowCount][columnCount]; for (int i = 0; i < rowCount; i++) { for (int j = 0; j < columnCount; j++) chocolate[i][j] = scanner.nextInt(); } check(chocolate, rowCount, columnCount); writer.flush(); writer.close(); } private void check(int[][] chocolate, int rowCount, int columnCount) { if (BreakRow(chocolate, rowCount, columnCount) || BreakColumn(chocolate, rowCount, columnCount)) writer.println("Yes"); else writer.println("No"); } private boolean BreakRow(int[][] chocolate, int rowCount, int columnCount) { for (int i = 0; i < rowCount - 1; i++) { boolean okRow = true; for (int j = 0; j < columnCount; j++) { if (chocolate[i][j] == chocolate[i + 1][j]) { okRow = false; break; } } if (okRow) return true; } return false; } private boolean BreakColumn(int[][] chocolate, int rowCount, int columnCount) { for (int i = 0; i < columnCount - 1; i++) { boolean okColumn = true; for (int j = 0; j < rowCount; j++) { if (chocolate[j][i] == chocolate[j][i + 1]) { okColumn = false; break; } } if (okColumn) return true; } return false; } } } |
Решение
Для решения данной задачи нужно представить шоколадку как двухмерный массив и проверить, можно ли разломать плитку шоколада ровно, то есть одинаковое ли количество «строк» и «столбцов» шоколада. Если так, то возвращается значение true и false в обратном случае.Для этого были созданы функции BreakRow и BreakColumn с возвращаемым значением типа boolean. Затем стоит проверить возвращаемое значение. Если одна из функций принимает значение true, то выводим положительный ответ. В противном случае ответ отрицательный.