анализ и сравнение, элементов матрицы Опции

[Злой человек]

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

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

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

[Человек, нуждающийся в помощи]

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

Спасибо

[Michael_Rybak]

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

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

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

...
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.

[Malice]

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

Тогда в примере из поста №2 будет только 1 прямоугольник, что неверно. Нужно после обнаружения прямоугольника закрашивать его неиспользуемым символом ( '.' ), тогда все ок будет.

[Michael_Rybak]

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

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

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

Сообщение отредактировано: Michael_Rybak - 16.10.2006 13:14

[Malice]

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

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

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


...1...
..213..
.42135.
6421357
.42135.
..213..
...1...
Аж 7 штук

[-Человек-]

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

[Michael_Rybak]

Как я понял, код ищет)) 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));