анализ и сравнение, элементов матрицы |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
анализ и сравнение, элементов матрицы |
Злой человек |
Сообщение
#1
|
Гость |
Дана матрица char[n][m]
Надо подсчитать количество прямоугольников(состоящих из различных символов) разных типов (‘.’ не учитывается) Пример ###. . .??..+. ###.= .??..+. ###. .. . ...+. . . . . ???.... . ???...... === ???. . .####.. # прямоугольников 2 ? прямоугольников 3 + прямоугольников 1 = прямоугольников 2 Подскажите, пожалуйста, хотя бы алгоритм... (как вывести матрицу я, конечно, знаю) Спасибо |
-Человек- |
Сообщение
#2
|
Гость |
#####
##### ##### ### . . ### . . ### . . Для такой матрицы, ответ 2. |
Michael_Rybak |
Сообщение
#3
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Хм, а для такой, получается, 4?
...#... ..###.. .#####. ####### .#####. ..###.. ...#... |
Человек, нуждающийся в помощи |
Сообщение
#4
|
Гость |
Я думаю, т.к. матрица задается из файла, то такой заморочки не будет)))
Матрица будет примерно как в примере(простите за тафталогию)... Спасибо |
Michael_Rybak |
Сообщение
#5
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Если матрица - примерно как в примере, то всё очень просто.
Считать нужно по левым верхним квадратикам. У каждого прямоугольника есть только один левый верхний квадратик , и отличается он от абсолютно всех остальных тем, что над ним, и слева от него символы - другие. Фрагмент кода будет выглядеть примерно так: ... |
Malice |
Сообщение
#6
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
|
Michael_Rybak |
Сообщение
#7
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
А что тогда делать с примером из поста 3?
И в посте 2, и в посте 3 прямоугольники пересекаются. Для такой ситуации нужно более четко сформулировать понятие прямоугольников, которые нас интересуют. ОП говорит, что "такой заморочки не будет". Сообщение отредактировано: Michael_Rybak - |
Malice |
Сообщение
#8
|
Профи Группа: Пользователи Сообщений: 705 Пол: Мужской Репутация: 20 |
А что тогда делать с примером из поста 3? И в посте 2, и в посте 3 прямоугольники пересекаются. Для такой ситуации нужно более четко сформулировать понятие прямоугольников, которые нас интересуют. Почему пересекаются, прикасаются только: ##### ##### ##### ### . . ### . . ### . . В четвертом посте не так красиво по моему алго получится, что-то типа этого: ...1... ..213.. .42135. 6421357 .42135. ..213.. ...1... Аж 7 штук |
-Человек- |
Сообщение
#9
|
Гость |
Как я понял, код ищет)) 1 прямоугольник, а как переходить от одного прямоугольника к другому? Использовать счетчик, который запоминает, какие элементы матрицы использованы?
|
Michael_Rybak |
Сообщение
#10
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Как я понял, код ищет)) 1 прямоугольник Нет. Код ищет все прямоугольники всех видов. Как известно, каждый символ имеет свой ASCII-код, число от 0 до 255 (если, конечно, текст записан в ASCII кодировке ). К примеру, решетка (#), если не ошибаюсь, 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)); |
Благодарный человек)) |
Сообщение
#11
|
Гость |
Спасибо за исчерпывающий ответ!!!
Но я, забыл упомянуть, что все это дело на pascal'е. Я долго думал, но так и не смог, некоторые опереторы из дельфийских в паскалевские перевести... |
klem4 |
Сообщение
#12
|
Perl. Just code it! Группа: Пользователи Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
Цитата некоторые опереторы из дельфийских в паскалевские перевести... Это какие например ? -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
-Человек- |
Сообщение
#13
|
Гость |
ВСЕМ СПАСИБО ОГРОМНОЕ!!!!!!!!!
Особенно Michael_Rybak!!! Но есть один вопрос: для чего вот это: fillchar(count, sizeof(count), 0);??? |
volvo |
Сообщение
#14
|
Гость |
Цитата Но есть один вопрос: для чего вот это: Чтобы не делать так:For i := 0 to 255 do count[i] := 0; У меня встречный вопрос: у тебя на клавиатуре кнопка F1 есть? Зачем она? |
Текстовая версия | 10.11.2024 16:33 |