Найдите максимальную красоту среди красот всех клеток и количество клеток, имеющих такую красоту

@Greenmars · Регистрация: 01.02.2016

Author24 — интернет-сервис помощи студентам

Помогите с Олимпиадой задачкой. Проходит не все тесты:

Текст задачи

Видимость звездочек (упрощенная версия)

Ограничения

ограничение времени на тест: 1 секунда
ограничение памяти на тест: 256 мегабайт
ввод: standard
вывод: standard

Задано прямоугольное поле из символов, состоящее из n строк по m символов в каждой строке. Каждый символ — это либо точка ('.’), либо звездочка '*’.

Назовем красотой клетки (i,j) число 0, если в этой клетке стоит точка и количество звездочек, которые видны из нее, если в (i,j) стоит звездочка. Из одной звездочки видно другую тогда и только тогда, когда они находятся в одной линии (строке или столбце) и между ними нет точек.

Найдите максимальную красоту среди красот всех клеток и количество клеток, имеющих такую красоту.

Входные данные
В первой строке задано два числа через пробел: n, m (1 ≤ n, m ≤ 400) — количество строк и столбцов в поле соответственно.

Во следующих n строках задано по m символов. Каждый символ — это либо точка ('.’), либо звездочка '*’.

Выходные данные
Выведите два числа — максимальную красоту среди красот всех клеток и количество клеток, имеющих такую красоту.

Примеры

input.txt	output.txt
4 4 .. ** ... .**	7 1

input.txt	output.txt
1 3 .	1 2

input.txt	output.txt
3 1 * . *	1 2

input.txt	output.txt
5 5 ***** . * * ***	9 16

А вот мой код на Паскале:

Pascal

   var a:array [1..400,1..400] of char; 
b:array [1..400,1..400] of longint; 
n,m,i,j,z,start,finish,cnt,max,ans:longint; 
begin 
readln(n,m); 
start:=0; 
finish:=0; 
for i:=1 to n do 
 begin 
 for j:=1 to m do 
 read(a[i,j]); 
 readln(); 
 end; 
for i:=1 to n do 
 for j:=1 to m do 
 begin 
 if (a[i,j]='*') and (start=0) then start:=j; 
 if a[i,j]='*' then inc(cnt); 
 if (a[i,j]='.') or (j=m) then 
 begin 
 if a[i,j]='.' then 
 finish:=j-1; 
 if (a[i,j]='*') and (j=m) then finish:=j; 
 if start<>0 then 
 begin 
 for z:= start to finish do 
 b[i,z]:=cnt; 
 cnt:=0; 
 start:=0; 
 end; 
 end; 
 end; 
cnt:=0; 
start:=0; 
for j:=1 to m do 
 for i:=1 to n do 
 begin 
 if (a[i,j]='*') and (start=0) then start:=i; 
 if a[i,j]='*' then inc(cnt); 
 if (a[i,j]='.') or (i=n) then 
 begin 
 if (a[i,j]='.') then 
 finish:=i-1; 
 if (a[i,j]='*') and (i=n) then 
 finish:=i; 
 if start<>0 then 
 begin 
 for z:=start to finish do 
 b[z,j]:=b[z,j]+cnt-1; 
 cnt:=0; 
 start:=0; 
 end; 
 end; 
 end; 
max:=0; 
ans:=1; 
for i:=1 to n do 
for j:=1 to m do 
if b[i,j]>max then 
 begin 
 max:=b[i,j]; 
 ans:=1 
 end 
else if b[i,j]=max then inc(ans); 
if max=0 then write(0,' ',0) else 
write(max,' ',ans); 
end.

P.S. Проходит 176 тестов из 195 возможных.

Если непонятен алгоритм - пишите, обязательно опишу.

@Cyborg Drone · 02.02.2016, 02:16

Не по теме:

Greenmars,

теме следует давать осмысленное название. Тему следует размещать в соответствующем разделе форума. Не нужно указывать язык программирования в названии темы.

Задание также необходимо публиковать в теме. Ссылки на задания и на ответы к заданиям зарещены.

И какие именно тесты не проходит - не написали. Телепаты у нас в отпуске, уж извините.

Ознакомьтесь с правилами форума.

@Greenmars · 02.02.2016, 10:19 **[ТС]**

Добрый день. Если бы я знала, какие тесты задача не проходит, было бы намного проще) так там просто написано, сайте, 176/195. И абсолютно ничего.
А как прикрепить по-другому текст задачи? Если она большая?

@bormant · 02.02.2016, 17:41

Всё намного проще:

Pascal

const mn=400;
var
  a: array [1..mn,1..mn] of Integer;
  m, n, i, j, k, p: Integer;
  c: Char;
begin
  ReadLn(m,n);
  for i:=1 to m do begin
    for j:=1 to n do begin
      Read(c); a[i,j]:=Ord(c='*');
    end; ReadLn;
  end;
  for i:=1 to m do begin
    j:=1;
    repeat
      while (j<=m) and (a[i,j]=0) do Inc(j); p:=j;
      while (j<=m) and (a[i,j]<>0) do Inc(j); k:=j-p-1;
      for p:=p to j-1 do Inc(a[i,p],k);
    until j>m;
  end;
  for j:=1 to n do begin
    i:=1;
    repeat
      while (i<=n) and (a[i,j]=0) do Inc(i); p:=i;
      while (i<=n) and (a[i,j]<>0) do Inc(i); k:=i-p-1;
      for p:=p to i-1 do Inc(a[p,j],k);
    until i>n;
  end;
  p:=0; k:=0;
  for i:=1 to m do for j:=1 to n do
    if a[i,j]>p then begin
      p:=a[i,j]; k:=1;
    end else if a[i,j]=p then Inc(k);
  WriteLn(p,' ',k);
end.

@Greenmars · 02.02.2016, 22:12 **[ТС]**

В принципе суть одна и та же.
А дело было вот в чем ( я помповому этих несчастных тестов)
Вариант если во входном файле такая матрица:
....
....
....

Исходя из увиденного, красота матрицы 0.
Но, есть одно но. Количество будет равно не 0, а 12, ну или же m*n.

Добавлено через 14 минут
bormant,
А не можете ли вы пояснить действия?

Добавлено через 10 минут
bormant, Спасибо большое. Я понял, в чем ошибка.
В принципе суть одна и та же.
А дело было вот в чем ( я помповому этих несчастных тестов)
Вариант если во входном файле такая матрица:
....
....
....

Исходя из увиденного, красота матрицы 0.
Но, есть одно но. Количество будет равно не 0, а 12, ну или же m*n.

@bormant · 02.02.2016, 22:25

Сообщение от Greenmars

пояснить действия?

7-12: читаем матрицу
13-20: обрабатываем по строкам, считаем длину непрерывного фрагмента, увеличиваем каждый элемент на длину фрагмента
21-28: обрабатываем по столбцам, аналогично
29-33: ищем максимум и количество его вхождений
34: вывод результата

@Greenmars · 02.02.2016, 22:29 **[ТС]**

Не по теме:

bormant, во-первых, большое спасибо:), а во-вторых, (это я сейчас совсем не по теме) не могли бы вы мне помочь. Как сделать так, чтобы и условие задачи было в теме и примеры. А то модератор отредактировал, а я найти не могу, как так сделать.

@bormant · 02.02.2016, 22:46

Не по теме:

Greenmars,
уже никак. Сообщение можно отредактировать в течение 5 минут после отправки.
Можете дополнительно попросить модератора изменить ваше сообщение. Можете оставить как есть, условие ведь по-прежнему доступно по нажатию на спойлер.
Просто учтите замечания на будущее.

@Greenmars · 02.02.2016, 22:50 **[ТС]**

Не по теме:

bormant, а при создании новой темы, как сделать так, чтобы условие задачи появлялось по нажатию на значок со знаком "+"?(спойлер, вроде, так называется.)
И чтобы тесты в таблицу поместить? Где-нибудь есть информация по созданию тем?

@Cyborg Drone · 02.02.2016, 22:52

Не по теме:

Greenmars, отредактировать? Скажите, как. Спойлеры, что ли, поубирать, наверное, кроме спойлера с "ограничениями"? Если честно, то я не понял Вашего вопроса в посте #3. Поэтому и не стал ничего отвечать. Потому что ответ очевиден: перепечатывайте/копируйте.

@Greenmars · 02.02.2016, 22:57 **[ТС]**

Не по теме:

Cyborg Drone, извините за некорректный вопрос. Сейчас напишу заново.
Я хочу создать новую тему, как мне оформить в своей теме текст задачи, ограничения и примеры так же, как отредактировал модератор в данной теме? С помощью каких функций?
Иными словами, как сделать такие спойлеры с Текстом задачи, ограничениями и примерами?

@Cyborg Drone · 02.02.2016, 23:00

Не по теме:

Сообщение от Greenmars

чтобы условие задачи появлялось по нажатию на значок со знаком "+"

Нет, перепечатывать/копировать. Форум никак не связан с псевдоолимпийскими/псевдообучающими сайтами.

Сообщение от Greenmars

тесты в таблицу поместить

Для этого нужно немножко уметь работать с BB-кодом TABLE. Есть тонкости при размещении нескольких строк в одной ячейке таблицы.

Сообщение от Greenmars

Где-нибудь есть информация по созданию тем?

Внизу окна для ввода сообщения есть "Справка по BB-кодам" и "Как работать в редакторе сообщений". Ниже окна редактора сообщения есть редактор формул. Справка по нему - левее и ниже окна для ввода формул.

@Greenmars · 02.02.2016, 23:01 **[ТС]**

Не по теме:

Cyborg Drone, спасибо

@Cyborg Drone · 02.02.2016, 23:02

Не по теме:

Сообщение от Greenmars

как отредактировал модератор в данной теме

Это был я. В принципе, большинство BB-кодов есть в шапке окна редактора сообщений, лучше - если Вы переключите редактор в расширенный режим, тогда можно сообщение предварительно просматривать.

@bormant · 02.02.2016, 23:06

Не по теме:

Greenmars,
в редакторе сообщений есть кнопка с "+" (верхний ряд, 10 слева), она вставляет тэги [ SPOILER ] [ /SPOILER ] (без пробелов, можно вписать руками), всё, что между ними, будет свернуто. Если в первом тэге дописать [ SPOILER=Текст задачи ], то именно этот текст станет заголовком спойлера.

@Cyborg Drone · 02.02.2016, 23:30

Не по теме:

Ещё совет по таблицам. Первая таблица из примеров

input.txt	output.txt
4 4 .. ** ... .**	7 1

на самом деле выглядит так:

[TABLE]input.txt|output.txt
[FONT="Courier New"]4 4[LEFT]..**[/LEFT]****[LEFT]..*.[/LEFT]*.**[/FONT]|[FONT="Courier New"]7 1[/FONT][/TABLE]

Чтобы получить символы одинаковой ширины, использован моноширинный шрифт, в данном случае, Courier New.
иначе бы получилось

input.txt	output.txt
4 4 .. ** ... .**	7 1

Для переноса текста на следующую строку в пределах одной и той же ячейки таблицы, используются BB-коды выравнивания текста, в данном случае, [LEFT][/LEFT], но можно использовать [CENTER][/CENTER] или [RIGHT][/RIGHT]. Коды форматирования - во второй строчке, 3, 4, 5 кнопочки в расширенном режиме.

Можно, конечно, любой код и вручную напечатать. Очень часто так и делаю.

@Cyborg Drone
	02.02.2016, 02:16 #2
	Не по теме: Greenmars, теме следует давать осмысленное название. Тему следует размещать в соответствующем разделе форума. Не нужно указывать язык программирования в названии темы. Задание также необходимо публиковать в теме. Ссылки на задания и на ответы к заданиям зарещены. И какие именно тесты не проходит - не написали. Телепаты у нас в отпуске, уж извините. Ознакомьтесь с правилами форума. 0

@Greenmars 0 / 0 / 0 Регистрация: 01.02.2016 Сообщений: 75
	02.02.2016, 10:19 [ТС]	3
	Добрый день. Если бы я знала, какие тесты задача не проходит, было бы намного проще) так там просто написано, сайте, 176/195. И абсолютно ничего. А как прикрепить по-другому текст задачи? Если она большая? 0

@Greenmars 0 / 0 / 0 Регистрация: 01.02.2016 Сообщений: 75
	02.02.2016, 22:12 [ТС]	5
	В принципе суть одна и та же. А дело было вот в чем ( я помповому этих несчастных тестов) Вариант если во входном файле такая матрица: .... .... .... Исходя из увиденного, красота матрицы 0. Но, есть одно но. Количество будет равно не 0, а 12, ну или же mn. Добавлено через 14 минут* bormant, А не можете ли вы пояснить действия? Добавлено через 10 минут bormant, Спасибо большое. Я понял, в чем ошибка. В принципе суть одна и та же. А дело было вот в чем ( я помповому этих несчастных тестов) Вариант если во входном файле такая матрица: .... .... .... Исходя из увиденного, красота матрицы 0. Но, есть одно но. Количество будет равно не 0, а 12, ну или же m*n. 0

@bormant Модератор 7769 / 4598 / 2823 Регистрация: 22.11.2013 Сообщений: 13,076 Записей в блоге: 1
	02.02.2016, 22:25	6
	Сообщение от Greenmars пояснить действия? 7-12: читаем матрицу 13-20: обрабатываем по строкам, считаем длину непрерывного фрагмента, увеличиваем каждый элемент на длину фрагмента 21-28: обрабатываем по столбцам, аналогично 29-33: ищем максимум и количество его вхождений 34: вывод результата 1

@Greenmars
	02.02.2016, 22:29 [ТС] #7
	Не по теме: bormant, во-первых, большое спасибо:), а во-вторых, (это я сейчас совсем не по теме) не могли бы вы мне помочь. Как сделать так, чтобы и условие задачи было в теме и примеры. А то модератор отредактировал, а я найти не могу, как так сделать. 0

@bormant
	02.02.2016, 22:46 #8
	Не по теме: Greenmars, уже никак. Сообщение можно отредактировать в течение 5 минут после отправки. Можете дополнительно попросить модератора изменить ваше сообщение. Можете оставить как есть, условие ведь по-прежнему доступно по нажатию на спойлер. Просто учтите замечания на будущее. 0

@Greenmars
	02.02.2016, 22:50 [ТС] #9
	Не по теме: bormant, а при создании новой темы, как сделать так, чтобы условие задачи появлялось по нажатию на значок со знаком "+"?(спойлер, вроде, так называется.) И чтобы тесты в таблицу поместить? Где-нибудь есть информация по созданию тем? 0

@Cyborg Drone
	02.02.2016, 22:52 #10
	Не по теме: Greenmars, отредактировать? Скажите, как. Спойлеры, что ли, поубирать, наверное, кроме спойлера с "ограничениями"? Если честно, то я не понял Вашего вопроса в посте #3. Поэтому и не стал ничего отвечать. Потому что ответ очевиден: перепечатывайте/копируйте. 0

@Greenmars
	02.02.2016, 22:57 [ТС] #11
	Не по теме: Cyborg Drone, извините за некорректный вопрос. Сейчас напишу заново. Я хочу создать новую тему, как мне оформить в своей теме текст задачи, ограничения и примеры так же, как отредактировал модератор в данной теме? С помощью каких функций? Иными словами, как сделать такие спойлеры с Текстом задачи, ограничениями и примерами? 0

@Cyborg Drone
	02.02.2016, 23:00 #12
	Не по теме: Сообщение от Greenmars чтобы условие задачи появлялось по нажатию на значок со знаком "+" Нет, перепечатывать/копировать. Форум никак не связан с псевдоолимпийскими/псевдообучающими сайтами. Сообщение от Greenmars тесты в таблицу поместить Для этого нужно немножко уметь работать с BB-кодом TABLE. Есть тонкости при размещении нескольких строк в одной ячейке таблицы. Сообщение от Greenmars Где-нибудь есть информация по созданию тем? Внизу окна для ввода сообщения есть "Справка по BB-кодам" и "Как работать в редакторе сообщений". Ниже окна редактора сообщения есть редактор формул. Справка по нему - левее и ниже окна для ввода формул. 0

@Greenmars
	02.02.2016, 23:01 [ТС] #13
	Не по теме: Cyborg Drone, спасибо 0

@Cyborg Drone
	02.02.2016, 23:02 #14
	Не по теме: Сообщение от Greenmars как отредактировал модератор в данной теме Это был я. В принципе, большинство BB-кодов есть в шапке окна редактора сообщений, лучше - если Вы переключите редактор в расширенный режим, тогда можно сообщение предварительно просматривать. 0

@bormant
	02.02.2016, 23:06 #15
	Не по теме: Greenmars, в редакторе сообщений есть кнопка с "+" (верхний ряд, 10 слева), она вставляет тэги [ SPOILER ] [ /SPOILER ] (без пробелов, можно вписать руками), всё, что между ними, будет свернуто. Если в первом тэге дописать [ SPOILER=Текст задачи ], то именно этот текст станет заголовком спойлера. 1

Найдите максимальную красоту среди красот всех клеток и количество клеток, имеющих такую красоту

Решение