Счастливые случаи
Счастливый случай — это лотерея. Каждый лотерейный билет имеет игровое поле и закрытую область. Игровое поле представляет собой прямоугольник размера $r \times c$, заполненный числами. Закрытая область скрывает номер строки и колонки, на пересечении которых находится игровая ячейка.
Существует четыре возможных выигрышных направления: вверх, вниз, влево и вправо. Направление считается выигрышным, если все числа в этом направлении от игровой ячейки в точности меньше числа в самой игровой ячейке. Если игровая ячейка находится на краю таблицы, то Вы автоматически имеете выигрышное направление!
Входные данные
В первой строке находятся два целых числа $r$ и $c$ $(1 \leqslant r, c \leqslant 100)$ — количество строк и колонок в таблице.
Каждая из следующих $r$ строк содержит $c$ чисел — значения на игровом поле. Каждое число положительно и не превосходит 1000.
Выходные данные
Вывести одно число $w$ — общее количество выигрышных направлений для заданной таблицы.
Тесты
| # | ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
|---|---|---|
| 1 | $1$ $1$ $4$ |
$4$ |
| 2 | $2$ $4$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ |
$12$ |
| 3 | $3$ $2$ $10$ $10$ $10$ $10$ $4$ $5$ |
$13$ |
| 4 | $2$ $2$ $1$ $2$ $3$ $4$ |
$12$ |
| 5 | $0$ $0$ | $0$ |
Код программы
|
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 |
import java.util.Scanner; class Main { public static void main (String[] args) throws java.lang.Exception { int w = 0, a, b, l, d; Scanner scan = new Scanner(System.in); int r = scan.nextInt(); int c = scan.nextInt(); int[][] x = new int [r][r]; for (int i = 0; i < r; i++) x[i] = new int[c]; for (int i = 0; i < r; i++){ for (int j = 0; j < c; j++){ x[i][j] = scan.nextInt(); } } for (int i = 0; i < r; i++){ for (int j = 0; j < c; j++){ a = b = l = d = 1; for (int q = 0; q < i; q++){ if (x[i][j] <= x[q][j]) a = 0; } for (int q = i+1; q < r; q++){ if (x[i][j] <= x[q][j]) b = 0; } for (int k = 0; k < j; k++){ if (x[i][j] <= x[i][k]) l = 0; } for (int k = j+1; k < c; k++){ if (x[i][j] <= x[i][k]) d = 0; } w+= a + b + l + d; } } System.out.print(w); } } |
Решение задачи
Решение данной задачи состоит в том, чтобы создать цикл, который будет сравнивать все элементы массива. Изначально у нас будут четыре переменных, которые отвечают за каждую из сторон массива, равные единице. Далее мы сравниваем каждый элемент строки с последующими в нужном направлении и если он не является выигрышным, то соответствующей переменной задаем значение ноль. Просуммировав все «выигрышные случаи» мы узнаем количество выигрышных направлений.
Ссылки
• Задача на e-olymp.
• Решение на сайте ideone.