Форум программистов, компьютерный форум, киберфорум
Наши страницы
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
Greenmars
0 / 0 / 0
Регистрация: 01.02.2016
Сообщений: 75
1

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

01.02.2016, 23:57. Просмотров 874. Ответов 15
Метки нет (Все метки)

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

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

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

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

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

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


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

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

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

Примеры
input.txtoutput.txt
4 4
..**
****
..*.
*.**
7 1

input.txtoutput.txt
1 3
*.*
1 2

input.txtoutput.txt
3 1
*
.
*
1 2

input.txtoutput.txt
5 5
*****
*.***
*****
*****
*****
9 16


А вот мой код на Паскале:
Pascal
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
60
61
62
63
64
65
66
67
   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 возможных.

Если непонятен алгоритм - пишите, обязательно опишу.
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.02.2016, 23:57
Ответы с готовыми решениями:

Напишите пожалуста программу :которая по заданному номеру клетки даст номер всех клеток,имеющих с ней общую сторону
Клетки шахматной доски пронумерованы от 1 до 64 по строчкам, слева на право и...

Определить число черных и белых клеток на доске
Не могу понять где ошибка. Program Chess; var F, M, N:integer; A,B:real;...

Дано клеточное поле, часть клеток занята препятствиями
Дано клеточное поле, часть клеток занята препятствиями. Необходимо попасть из...

Шахматная доска содержит 8х8 клеток... Одномерный массив, содержащий N элементов...Из данного текста выпишите слова, длины которых меньше N...
Задача 1. Шахматная доска содержит 8х8 клеток. Горизонтали и вертикали...

Вывести шахматную доску с изображением слона и всех клеток, в которые он может походить
Условие Слон — шахматная фигура, которая может двигаться на любое число клеток...

15
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
bormant
Модератор
Эксперт Pascal/DelphiЭксперт NIX
4007 / 2635 / 2124
Регистрация: 22.11.2013
Сообщений: 7,415
02.02.2016, 17:41 4
Лучший ответ Сообщение было отмечено Greenmars как решение

Решение

Всё намного проще:
Pascal
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
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.
1
Greenmars
0 / 0 / 0
Регистрация: 01.02.2016
Сообщений: 75
02.02.2016, 22:12  [ТС] 5
В принципе суть одна и та же.
А дело было вот в чем ( я помповому этих несчастных тестов)
Вариант если во входном файле такая матрица:
....
....
....

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

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

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

Исходя из увиденного, красота матрицы 0.
Но, есть одно но. Количество будет равно не 0, а 12, ну или же m*n.
0
bormant
Модератор
Эксперт Pascal/DelphiЭксперт NIX
4007 / 2635 / 2124
Регистрация: 22.11.2013
Сообщений: 7,415
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
Cyborg Drone
02.02.2016, 23:30     Найдите максимальную красоту среди красот всех клеток и количество клеток, имеющих такую красоту
  #16

Не по теме:

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

input.txtoutput.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.txtoutput.txt
4 4
..**
****
..*.
*.**
7 1

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

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

0
02.02.2016, 23:30
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2016, 23:30
Привет! Вот еще темы с ответами:

Жизнь клеток - Перевод решения из PascalABC
Всем здравствуйте! Написал прогу для сдачи преподавателю. Предмет &quot;Компьютерное...

Определите, на сколько клеток будет сдвинута деталь
Доброго времени суток, форумчане. Я не силен в программировании, есть задача,...

Процедура для закрашивания клеток шахматной доски
Ребят, передо мной задача: нарисовать шахматную доску. Я только начинающий и...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
16
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru