IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> анализ и сравнение, элементов матрицы
сообщение
Сообщение #1


Гость






Дана матрица char[n][m]
Надо подсчитать количество прямоугольников(состоящих из различных символов) разных типов (‘.’ не учитывается)
Пример
###. . .??..+.
###.= .??..+.
###. .. . ...+.
. . . . ???.... .
???...... ===
???. . .####..

# прямоугольников 2
? прямоугольников 3
+ прямоугольников 1
= прямоугольников 2

Подскажите, пожалуйста, хотя бы алгоритм... (как вывести матрицу я, конечно, знаю)
Спасибо
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






#####
#####
#####
### . .
### . .
### . .

Для такой матрицы, ответ 2.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Хм, а для такой, получается, 4?

...#...
..###..
.#####.
#######
.#####.
..###..
...#...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






Я думаю, т.к. матрица задается из файла, то такой заморочки не будет)))
Матрица будет примерно как в примере(простите за тафталогию)...

Спасибо
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Если матрица - примерно как в примере, то всё очень просто.

Считать нужно по левым верхним квадратикам. У каждого прямоугольника есть только один левый верхний квадратик smile.gif, и отличается он от абсолютно всех остальных тем, что над ним, и слева от него символы - другие.

Фрагмент кода будет выглядеть примерно так:

...
var count: array[0 .. 255] of longint;
...
begin
...
fillchar(count, sizeof(count), 0);
for i := 1 to height do
for j := 1 to width do
if s[i, j] <> '.' then
if (i = 1) or (s[i - 1, j] <> s[i, j]) then //сверху нету такого же
if (j = 1) or (s[i, j - 1] <> s[i, j]) then //слева нету такого же
//увеличиваем количество найденных прямоугольников,
//составленных из символов с кодом ord(s[i, j])
Inc(count[ord(s[i, j])]);
...
end.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Michael_Rybak @ 16.10.2006 1:22) *

Считать нужно по левым верхним квадратикам.

Тогда в примере из поста №2 будет только 1 прямоугольник, что неверно. Нужно после обнаружения прямоугольника закрашивать его неиспользуемым символом ( '.' ), тогда все ок будет.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


А что тогда делать с примером из поста 3?

И в посте 2, и в посте 3 прямоугольники пересекаются. Для такой ситуации нужно более четко сформулировать понятие прямоугольников, которые нас интересуют.

ОП говорит, что "такой заморочки не будет".

Сообщение отредактировано: Michael_Rybak -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Профи
****

Группа: Пользователи
Сообщений: 705
Пол: Мужской

Репутация: -  20  +


Цитата(Michael_Rybak @ 16.10.2006 14:10) *

А что тогда делать с примером из поста 3?
И в посте 2, и в посте 3 прямоугольники пересекаются. Для такой ситуации нужно более четко сформулировать понятие прямоугольников, которые нас интересуют.

Почему пересекаются, прикасаются только:
#####
#####
#####

### . .
### . .
### . .

В четвертом посте не так красиво по моему алго получится, что-то типа этого:


...1...
..213..
.42135.
6421357
.42135.
..213..
...1...

Аж 7 штук smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Как я понял, код ищет)) 1 прямоугольник, а как переходить от одного прямоугольника к другому? Использовать счетчик, который запоминает, какие элементы матрицы использованы?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(-Человек- @ 16.10.2006 17:54) *

Как я понял, код ищет)) 1 прямоугольник



Нет. Код ищет все прямоугольники всех видов.

Как известно, каждый символ имеет свой ASCII-код, число от 0 до 255 (если, конечно, текст записан в ASCII кодировке smile.gif ). К примеру, решетка (#), если не ошибаюсь, 35.

Вложенным циклом я пробегаю по всем клеткам массива:

Цитата
Код
  for i := 1 to height do
    for j := 1 to width do


Затем я смотрю, что эта клетка - не пустая:

Цитата
Код
     if s[i, j] <> '.' then


Затем я проверяю, что клетка принадлежит верхней границе своего прямоугольника. Для этого смотрю, что сверху над этой клеткой либо кончается поле (i = 1), либо находится клетка с другим символом:

Цитата
Код
        if (i = 1) or (s[i - 1, j] <> s[i, j]) then //сверху нету такого же


Затем - аналогичная проверка слева:

Цитата
Код
          if (j = 1) or (s[i, j - 1] <> s[i, j]) then //слева нету такого же


Если все условия выполнились, это означает, что мы нашли левую верхнюю клетку некоторого прямоугольника (если, конечно, случаи из постов 2 и 3 исключены).

Чтобы учесть этот факт, возьмем ASCII-код символа в текущей клетке:

Цитата
Код
ord(s[i, j])


В начале заведем массив из 256 счетчиков:
Цитата

Код
var count: array[0 .. 255] of longint;
...
begin
...
  fillchar(count, sizeof(count), 0);


Найдя прямоугольник, состоящий, например, из решеток, увеличим счетчик с индексом 35. В общем случае:

Цитата
Код
            Inc(count[ord(s[i, j])]);


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

Чтобы вывести статистику, ищем счетчики с ненулевыми показателями:

Код
for i := 0 to 255 do
  if count[i] > 0 then
    Writeln('Found ', count[i], ' rectangles built with symbol ', Chr(i));
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Гость






Спасибо за исчерпывающий ответ!!!
Но я, забыл упомянуть, что все это дело на pascal'е. Я долго думал, но так и не смог, некоторые опереторы из дельфийских в паскалевские перевести...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


Цитата
некоторые опереторы из дельфийских в паскалевские перевести...


Это какие например ? blink.gif


--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Гость






ВСЕМ СПАСИБО ОГРОМНОЕ!!!!!!!!!
Особенно Michael_Rybak!!! cool.gif

Но есть один вопрос: для чего вот это:

fillchar(count, sizeof(count), 0);???
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Гость






Цитата
Но есть один вопрос: для чего вот это:
Чтобы не делать так:
For i := 0 to 255 do count[i] := 0;


У меня встречный вопрос: у тебя на клавиатуре кнопка F1 есть? Зачем она?
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 21:19
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name