Массив символов. (Алгоритм нахождения прямоуг - в)

 
0
 
C++
ava
ioManip | 17.02.2013, 06:43
Привет, VinGrad! smile 

Есть задачка.
Там говориться, что массив кодируется символами ( #, +, -, ?) и '.' - это пустые места. Каждый раз массив задается рандомно. И нужно посчитать сколько прямоуг. в массиве.
Так вот меня смутило то, как можно написать такой алгоритм, если массив каждый раз разный, ведь вся матрица может быть одним большим прямоугольником или их и вовсе может не быть.

Может есть идейки? А то я в тупике  smile 
Ответы (3)
ava
feodorv | 17.02.2013, 06:47 #
Ну, Вы не написали, что каждый из символов #, +, -, ? изначально принадлежит какому-нибудь прямоугольнику. Задача становится проще.
  • делаете копию массива (мы его будем менять)
  • обходите копию массив сверху вниз слева направо; если текущий элемент '.', то переходите к следующему элементу, если #, +, -, ?, то переходите к следующему шагу
  • увеличиваете счётчик прямоугольников на 1, счётчик выбирается в зависимости от значения текущего элемента  - #, +, -, ?
  • запоминаете текущий символ (один из #, +, -, ?) и совершаете ещё один обход с текущего места сверху вниз слева направо до тех пор, пока значения элементов совпадают с запомненным символом (таким образом будут просмотрены все прилегающие к текущему однотипные с ним элементы, то есть будет пройден весь прямоугольник); все такие элементы превращаете в '.' (обещанное изменение) - они не будут мешаться в дальнейшем.
ava
NightmareZ | 17.02.2013, 08:11 #

#include <stdio.h>
#include <stdlib.h>

void printArray(char* chars, int m, int n)
{
    int i, j;

    for (j = 0; j < n; ++j)
    {
        for (i = 0; i < m; ++i)
            printf("%c", chars[j * m + i]);

        printf("\n");
    }

    printf("\n");
}

void calcRects(char* chars, int m, int n)
{
    int i, j, k;
    char curr;
    int counts[4] = { 0 };
    char ch[4] = { '#', '?', '+', '=' };

    for (j = 0; j < n; ++j)
        for (i = 0; i < m; ++i)
        {
            curr = chars[j * m + i];

            if (curr != '.' &&
                (i > 0 && chars[j * m + i - 1] != curr || i == 0) &&
                (j > 0 && chars[(j - 1) * m + i] != curr || j == 0))
            {
                for (k = 0; k < sizeof(ch); ++k)
                    if (ch[k] == curr)
                    {
                        ++counts[k];
                        break;
                    }
            }
        }

    for (i = 0; i < sizeof(ch); ++i)
        printf("%c rectangles: \t%d\n", ch[i], counts[i]);
}

#define M 11
#define N 6

int main(void)
{
    char chars[N][M] =
    {
        { '#', '#', '#', '.', '.', '.', '?', '?', '.', '+', '.' },
        { '#', '#', '#', '.', '=', '.', '?', '?', '.', '+', '.' },
        { '#', '#', '#', '.', '.', '.', '.', '.', '.', '+', '.' },
        { '.', '.', '.', '.', '.', '?', '?', '?', '.', '.', '.' },
        { '?', '?', '?', '.', '.', '.', '.', '.', '.', '=', '=' },
        { '?', '?', '?', '.', '.', '.', '#', '#', '#', '.', '.' }
    };

    printArray((char*)chars, M, N);
    calcRects((char*)chars, M, N);

    return EXIT_SUCCESS;
}
ava
ioManip | 19.02.2013, 14:33 #
feodorv, Спасибо за алгоритм.

NightmareZ, Спасибо за пример реализации.
Зарегистрируйтесь или войдите, чтобы написать.
Фирма дня
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Участники
advanced
Отправить