7623. Счастливые случаи

Счастливый случай – это лотерея. Каждый лотерейный билет имеет игровое поле и закрытую область. Игровое поле представляет собой прямоугольник размера r × c, заполненный числами. Закрытая область скрывает номер строки и колонки, на пересечении которых находится игровая ячейка.

Существует четыре возможных выигрышных направления: вверх, вниз, влево и вправо. Направление считается выигрышным, если все числа в этом направлении от игровой ячейки в точности меньше числа в самой игровой ячейке. Если игровая ячейка находится на краю таблицы, то Вы автоматически имеете выигрышное направление!

Ларри хочет выбрать билет, который имеет максимальное общее количество выигрышных направлений для всех возможных игровых ячеек. Напишите программу, которая определяет это количество для заданного игрового билета.

Вход. В первой строке находятся два целых числа r и c (1 ≤ r, c ≤ 100) – количество строк и колонок в таблице.

Каждая из следующих r строк содержит c чисел – значения на игровом поле. Каждое число положительно и не превосходит 1000.

Выход. Вывести одно число w – общее количество выигрышных направлений для заданной таблицы.

Пример входа	Пример выхода
3 4 5 3 9 10 1 8 8 2 4 3 4 3	25

РЕШЕНИЕ

математика

Анализ алгоритма

Пусть функция check() вычисляет количество ячеек, для которых левое направление будет выигрышным. Для каждой i-ой строки следует найти такое количество элементов m[i][j], что все числа, стоящие в строке до него, строго меньше m[i][j].

Далее следует повернуть прямоугольную таблицу по часовой стрелке на 90° и для нее найти число ячеек, для которых левое направление выигрышное. Повторим поворот и подсчет ячеек еще два раза.

Пример

Итого имеем:

Реализация алгоритма

Объявим два массива для хранения таблицы.

#define MAX 101

int m[MAX][MAX], m1[MAX][MAX];

Функция check подсчитывает количество ячеек res, для которых левое направление будет выигрышным.

int check(void)

{

int i, j, s, res = 0;

for(i = 0; i < r; i++)

{

for(s = j = 0; j < c; j++)

if (m[i][j] > s)

{

s = m[i][j];

res++;

}

}

return res;

}

Вращаем прямоугольник по часовой стрелке. Сначала вращая переносим данные из m в m1. Далее копируем m1 в m.

void rotate(void)

{

int i, j, s;

memset(m1,0,sizeof(m1));

for(i = 0; i < r; i++)

for(j = 0; j < c; j++)

m1[j][r-i-1] = m[i][j];

memcpy(m,m1,sizeof(m));

s = r; r = c; c = s;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&r,&c);

for(i = 0; i < r; i++)

for(j = 0; j < c; j++)

scanf("%d",&m[i][j]);

Прибавляем к res количество ячеек, для которых левое направление будет выигрышным. После чего поворачиваем таблицу. Повторяем 4 раза (левое, нижнее, правое, верхнее направления).

res = 0;

for(i = 0; i < 4; i++)

{

res += check();

rotate();

}

Выводим ответ.

printf("%d\n",res);