Форум программистов, компьютерный форум CyberForum.ru

Алгоритм поиска в матрице - C++

Восстановить пароль Регистрация
 
Fatosha
0 / 0 / 0
Регистрация: 12.10.2013
Сообщений: 153
06.12.2013, 23:23     Алгоритм поиска в матрице #1
Народ, если поможете, буду вообще супер благодарен.
Задание такое:"Найти квадрат максимальной площади в матрице и выписать координаты его диагонали"

Поясняю. Есть матрица
1 1 1 1 1
1 0 0 1 1
1 0 0 1 1
1 1 1 1 0

Надо, что бы выписал 0 0 3 3 т.к. это координаты диагонали квадрата, который имеет максимальную площадь

Вообще затуп глобальный, помогите с поиском алгоритма.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.12.2013, 23:23     Алгоритм поиска в матрице
Посмотрите здесь:

C++ Матрицы, алгоритм поиска
C++ Алгоритм поиска в глубину
Алгоритм поиска А* C++
Алгоритм поиска в ширину C++
C++ Алгоритм поиска
C++ Простые алгоритм поиска?
Добавить методы поиска медианного элемента в матрице и векторе C++
C++ Алгоритм поиска(не находит)

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
RQdan
65 / 65 / 17
Регистрация: 26.10.2013
Сообщений: 198
07.12.2013, 02:44     Алгоритм поиска в матрице #2
а - массив;n и m - кол-во строк и столбцов массива
C++
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
int sum,n=4,m=5;
    int k,x,y;
    bool cont=true;
 
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }
 
    if(n<m)k=n-1;else k=m-1;//определяем наибольшую возможную сторону квадрата
    while((cont)&&(k>0))//сторона квадратов на уменьшение
    {
        x=0;
        while((cont) && (x<n-k))//движение верхнего левого угла квадрата со стороной k с начала координат
        {
            y=0;
            while((cont) && (y<m-k))
            {
                sum=0;//периметр квадрата
                for(int i=1;i<k;i++)//вычисление периметра квадрата со стороной k
                {
                    sum+=a[x][y+i]+a[x+i][y]+a[x+k][y+i]+a[x+i][y+k];
                }
                sum+=a[x][y]+a[x][y+k]+a[x+k][y]+a[x+k][y+k];
                if(sum==k*4) cont=false;else y++;//если периметр "полный" - нашелся квадрат с наибольшей площей
            }
            if(cont) x++;
        }
        if(cont)k--;
    }
    cout<<x<<" "<<y<<" "<<x+k<<" "<<y+k<<" "<<endl;
P.S. алгоритм расчитан на поиск квадратов со стороной не меньше 2. Для полноты картины в конце можно добавить несколько строчек на случай, если таких квадратов не нашлось - тогда ищется первая ячейка со значением 1 и проверяется матрица на наличие хотя бы одной не пустой ячейки.
Fatosha
0 / 0 / 0
Регистрация: 12.10.2013
Сообщений: 153
07.12.2013, 12:15  [ТС]     Алгоритм поиска в матрице #3
RQdan, Спасибо огромное, просто невероятно помог
Yandex
Объявления
07.12.2013, 12:15     Алгоритм поиска в матрице
Ответ Создать тему
Опции темы

Текущее время: 22:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru