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

Матрицы. Поиск области, заполненной единицами. C++ - C++

Восстановить пароль Регистрация
 
Monster-Lock
0 / 0 / 0
Регистрация: 21.12.2010
Сообщений: 9
21.12.2010, 19:56     Матрицы. Поиск области, заполненной единицами. C++ #1
Такая задача:
Дана матрица, заполненная нулями и единицами. Нужно вывести на экран максимальную область, заполненную единицами. Область должна быть прямоугольной, в остальном не имеет значения ее форма.
Код
#include "stdafx.h"
#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
     setlocale(LC_ALL,"");
     int mat[8][8];
     for(int i=0; i<8; i++)
          for(int j=0;j<8;j++)
               mat[j][i]=rand()%2+0;

     for(int i=0; i<8; i++){
          cout<<endl;
          for(int j=0;j<8;j++)
               cout<<mat[j][i]<<" ";
     }
int st=0; int sb=0; int qw=0, qe=0;;
int x=0,y=0;
     for(int i=0; i<8; i++){
          for(int j=0;j<8;j++){
               if(mat[j][i]==1){
                    x=i;
                    y=j;
                    while(mat[j][i]!=0){
                         st++;
                    }
               }
               for(int k=j;k<8;k++){
                    while(mat[k][st]!=0){
                         sb++;
                    }
               }
               for(int r=st; r!=0; r--){
                    qw=st;
                    while(mat[sb][r]!=0){
                         qw--;
                    }
               }
               for(int z=qw; z!=0; z--){
                    while(mat[z][qw]!=0){
                         qe=z;
                    }
               }
               if (x==qw && y==qe){
                    cout<<"это то: ";
                    for(int g=x; g<st; g++){
                         cout<<endl;
                         for(int h=y;h<sb;h++){
                              cout<<mat[g][h]<<" ";
                         }
                    }
               }

          }
     }

     cout<<endl;
     system("pause");
}
В коде зависает цикл. Долго отлаживал, так проблему и не нашел.
Правил таким образом:
Код
while(mat[st][i]!=0){
    st++;
}
за границы массива вроде не выходит, но цикл все равно виснет. Собственно говоря таких циклов 4, и проблема в них одна и та же.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.12.2010, 19:56     Матрицы. Поиск области, заполненной единицами. C++
Посмотрите здесь:

Вычислить сумму элементов матрицы в заштрихованной области C++
C++ Элементы матрицы умножить на скаляр C=5,2. Элементы третьего столбца заменить единицами
Среди столбцов заданной целочисленной матрицы, заполненной случайными числами, порядка n* n, найти столбец с элементами C++
Найти минимальный элемент в заштрихованной области матрицы C++
C++ Заменить все положительные элементы матрицы единицами
Найти наименьший элемент прямоугольной матрицы, заполненной случайными числами C++
C++ Заполнить массив единицами и минус единицами и поменять единицы и минус единицы местами
Заполнить первую половину матрицы размером n*n единицами, а вторую - нулями C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
21.12.2010, 22:38     Матрицы. Поиск области, заполненной единицами. C++ #2
Вообще-то алгоритм должен быть таким:
Встретилась в массиве 1.
1. Перебираем вправо элементы в этой строке пока встречаются одни 1 или пока не закончится строка. Сравнили площадь с уже имеющейся.
2. Смотрим вниз от элемента на котором остановились. Если там единица, то переходим к п.1, только просматриваем вправо элементы второй строки (но не более длинны первой).
и т.д. пока вниз не закончится столбец или не встретится 0.
Далее снова начинаем искать новую единицу в массиве ...
Yandex
Объявления
21.12.2010, 22:38     Матрицы. Поиск области, заполненной единицами. C++
Ответ Создать тему
Опции темы

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