VPF::Найти количество островков из единиц

Luster

Дата 29.7.2015, 11:38 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 29.7.2015

Репутация: нет
Всего: нет

Доброе времени суток! Я новичок в программировании. Мне не понятен вот этот код. Написан он очень уж умно. А мне нужен примитивный, просто код, что бы его можно было легко читать. А этот код даже "загуглив" практически каждую строчку, требует практики, что бы его понять. Может быт, кто- нибудь смог бы его переписать более просто? на базовом уровне?

Код

#include <cmath>
#include <fstream>
#include <iostream>
#include <set>
#include <string>
#include <utility>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::string                     T_str;
typedef std::pair   < int,  int     >   T_cell;
typedef std::set    < T_cell        >   T_cells;
/////////////////////////////////////////////////////////////////////////////////////////
void    go_to_cell_with_cells_and_visited_cells
    (
        T_cell                  cell,
        T_cells     const   &   cells,
        T_cells             &   visited_cells
    )
{
    visited_cells.insert( cell );
 
    for (
            auto
            adj_cell_it     =   cells.begin     ();
            adj_cell_it     !=  cells.end       ();
            ++adj_cell_it
        )
    {
        if  (
                    visited_cells.count( *adj_cell_it )     ==  0
 
                &&  (
                                abs( cell.first     -   adj_cell_it->first      )
                            +   abs( cell.second    -   adj_cell_it->second     )
                        ==  1
                    )
            )
        {
            go_to_cell_with_cells_and_visited_cells
                (
                    *adj_cell_it,
                    cells,
                    visited_cells
                );
        }
    }//for
}
/////////////////////////////////////////////////////////////////////////////////////////
int     get_islands_count_of( T_cells   const   &   cells )
{
    int         res_count   =   0;
    T_cells     visited_cells;
 
    for (
            auto
            cell_it     =   cells.begin     ();
            cell_it     !=  cells.end       ();
            ++cell_it
        )
    {
        if  (
                visited_cells.count( *cell_it )     ==  0
            )
        {
            ++res_count;
 
            go_to_cell_with_cells_and_visited_cells
                (
                    *cell_it,
                    cells,
                    visited_cells
                );
        }
    }//for
 
    return  res_count;
}
/////////////////////////////////////////////////////////////////////////////////////////
int     main()
{
    std::locale::global(std::locale(""));
 
    const   T_str   INPUT_FILENAME      =   "input.txt";
    const   T_str   OUTPUT_FILENAME     =   "output.txt";
 
    std::ifstream   ifile( INPUT_FILENAME );
    T_cells     cells;
 
    if( !ifile )
    {
        std::cout   <<  "Невозможно прочитать данные из файла."
                    <<  std::endl;
    }
    else
    {
        int     matr_dim    =   0;
        ifile   >>  matr_dim;
 
        for( int  i = 0; i < matr_dim; ++i )
        {
            for( int  j = 0; j < matr_dim; ++j )
            {
                int     cell_val    =   0;
                ifile   >>  cell_val;
 
                if( cell_val )
                {
                    cells.insert    (
                                        T_cell( i, j )
                                    );
                }
            }//for
        }//for
 
        std::ofstream   ofile( OUTPUT_FILENAME );
        ofile   <<  get_islands_count_of( cells );
    }//else
 
    system("pause");
}

этот код к такому заданию, только я не понял, в этом алгоритме есть обход в глубину или нету?

Задача Острова
Каждый элемент квадратной матрицы размеренности N x N равен нулю, либо
единице. Найдите количество «островов», образованных единицами. Под «островом»
понимается группа единиц (либо одна единица), со всех сторон окруженная нулями
(или краями матрицы). Единицы относятся к одному «острову», если из одной из них
можно перейти к другой «наступая» на единицы, расположенные в соседних клетках.
Соседними являются клетки, граничащие по горизонтали или вертикали.
Уточним, что одна единица тоже считается островом. Также предлагаю считывать
матрицу из файла.
Входные данные
В первой строке файла INPUT.TXT записано натуральное число N не больше 100 -
размер квадратной матрицы. В следующих N строках задаются элементы матрицы
через пробел.
Выходные данные
В файл OUTPUT.TXT выведите единственное число - количество островов.
Пример
INPUT.TXT
4

OUTPUT.TXT
5
1 0 1 1 1
0 0 0 0 0
1 1 1 0 1
0 1 0 0 1
0 0 0 1 1

Решение задачи
Итак, это классическая задача на поиск в глубину графа. Понятно, что надо
обходить матрицу и каким-то образом вычислять количество островов. Вариант решения такой: после того, как мы попадаем на остров, надо это зафиксировать
увеличив переменную-результат на единицу. Чтобы второй раз не посчитать один и
тот же остров, сразу после посещения необходимо его уничтожить, т.е. присвоить
всем клеткам острова значение ноль.
Поскольку тест задачи не слишком мал, стоит написать процедуру уничтожения
островов, назовем ее"count". Чтобы во время выполнения процедуру не "выскочить"
за пределы массива, сделаем его не размером N x N, а размеров N+2 x N+2, это даст
нам возможность окружить искомый массив размеромN x N нулями.

Модератор: не забываем пользоваться кнопочкой "Код"

Это сообщение отредактировал(а) bsa - 3.8.2015, 18:28

borisbn

Дата 31.7.2015, 12:46 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 4875
Регистрация: 6.2.2010
Где: Ростов-на-Дону

Репутация: 21
Всего: 135

Лови (как-то делал себе такое)

http://ideone.com/yUjfPg

Код


#include <stdio.h>
#include <locale.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdlib.h>
using namespace std;

const int ROWS = 7;
const int COLS = 10;
int array[ ROWS ][ COLS ] = {
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    {0, 0, 1, 1, 1, 1, 0, 0, 0, 0 },
    {0 ,0 ,1 ,1 ,0 ,1 ,0 ,1 ,0 ,0 },
    {0, 0, 1, 1, 1, 1, 0, 1, 1, 0 },
    {1, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
    {0, 1, 1, 1, 0, 0, 0, 0, 0, 0 }
};
bool watched[ ROWS ][ COLS ] = { 0 };


struct Rect
{
    int left;
    int top;
    int right;
    int bottom;
};
typedef vector< Rect > Objects;

void go( int y, int x, int y_inc, int x_inc, Rect & rect )
{
    y = y + y_inc;
    x = x + x_inc;
    //cout << y << " " << x << endl;
    if ( y >= 0 && y < ROWS && x >= 0 && x < COLS )
    {
        if ( array[ y ][ x ] != 0 && watched[ y ][ x ] == false )
        {
            //cout << "+" << endl;
            watched[ y ][ x ] = true;
            rect.left = std::min( rect.left, x );
            rect.top = std::min( rect.top, y );
            rect.right = std::max( rect.right, x );
            rect.bottom = std::max( rect.bottom, y );
            go( y, x, -1, -1, rect ); // up left
            go( y, x, -1, 0, rect );  // up
            go( y, x, -1, 1, rect );  // up right
            go( y, x, 0, -1, rect );  // left
            go( y, x, 0, 1, rect );   // right
            go( y, x, 1, 1, rect );   // down right
            go( y, x, 1, 0, rect );   // down
            go( y, x, 1, -1, rect );  // down left
        }
    }
}

int main()
{
    Objects objects;
    cout << "  |";
    for ( int x = 0; x < COLS; x++ )
    {
        cout << " " << x;
    }
    cout << endl;
    cout << "--|";
    for ( int x = 0; x < COLS; x++ )
    {
        cout << "--";
    }
    cout << endl;
    for ( int y = 0; y < ROWS; y++ )
    {
        cout << y << " | ";
        for ( int x = 0; x < COLS; x++ )
        {
            if ( array[ y ][ x ] != 0 && watched[ y ][ x ] == false )
            {
                Rect rect;
                rect.left = x;
                rect.top = y;
                rect.right = x;
                rect.bottom = y;
                go( y, x, 0, 0, rect );
                objects.push_back( rect );
            }
            cout << array[ y ][ x ] << ' ';
        }
        cout << endl; 
    }
    cout << endl;
    for ( Objects::const_iterator it = objects.begin(); it != objects.end(); ++it )
    {
        const Rect & rect = (*it);
        cout << "left = " << rect.left << " top = " << rect.top << " "
             << "right = " << rect.right << " bottom = " << rect.bottom
             << endl;
    }
}

--------------------

Женщины отличаются от программистов тем, что у них чары состоят из стрингов

Luster

Дата 31.7.2015, 16:28 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 7
Регистрация: 29.7.2015

Репутация: нет
Всего: нет

Спасибо большое, жаль что тут не с файла в файл. Переделаем.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Для новичков \| Следующая тема »