Форум по Delphi программированию



Вернуться   Форум по Delphi программированию > C/C++ > C/C++
Ник
Пароль
Регистрация <<         Правила форума         >> FAQ Пользователи Календарь Поиск Сообщения за сегодня Все разделы прочитаны

Ответ
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 29.07.2015, 11:43
Luster Luster вне форума
Прохожий
 
Регистрация: 29.07.2015
Сообщения: 5
Версия Delphi: visual studio
Репутация: 10
Лампочка Найти количество островков из единиц

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

Код:
#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 нулями.

Последний раз редактировалось lmikle, 29.07.2015 в 19:32.
Ответить с цитированием
  #2  
Старый 29.07.2015, 19:45
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 7,788
Версия Delphi: 7, XE3, 10.2
Репутация: 49089
По умолчанию

Ну, я бы тогда по твоему алгоритму сделал бы что-то типа:
Код:
var
  A : Array Of Integer; // Карта

// "Удаление" острова
procedure DeleteIsland(AI, AJ : Integer);
var
  I, J : Integer;
begin
  A[I,J] := 0;
  For I := AI-1 To AI+1 Do
    For J := AJ-1 To AJ+1 Do
      If (I >= Low(A)) And (I <= High(A)) And (J >= Low(A[i])) And (J <= High(A[i])) Then
        If A[I,J] = 1 Then DeleteIsland(I,J);
end;

// Подсчет островов
function CountIslands : Integer;
var
  I, J : Integer;
begin
  Result := 0;
  For I := Low(A) To High(A) Do
    For J := Low(A[i]) To High(A[i]) Do
      If A[I,J] = 1 Then
        Begin
          Inc(Result);
          DeleteIsland(I,J);
        End;
end;

Кратко:
CountIslands - пробегает по всем ячейкам матрицы и если находит 1, то увеличивает счетчик и вызывает процедуру удаления острова.
DeleteIsland - удаляет элемент острова в текущей ячейке, а потом рекурсивно вызывает себя для удалени всех соседних ячеек (если они равны 1). If с большим условием - что бы не вылететь за границу массива.
Ответить с цитированием
  #3  
Старый 29.07.2015, 19:47
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 7,788
Версия Delphi: 7, XE3, 10.2
Репутация: 49089
По умолчанию

Ой, не посмотрел, что надо на C/C++.
С другой стороны, алгоритм действия понятен. Дальше сам должен смочь перевести.
Ответить с цитированием
  #4  
Старый 29.07.2015, 23:44
Luster Luster вне форума
Прохожий
 
Регистрация: 29.07.2015
Сообщения: 5
Версия Delphi: visual studio
Репутация: 10
По умолчанию

что бы переделать, нужно знать паскаль. За попытку спасибо. Может быть еще будет и на с ++
Ответить с цитированием
  #5  
Старый 30.07.2015, 00:05
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 7,788
Версия Delphi: 7, XE3, 10.2
Репутация: 49089
По умолчанию

Да что тут знать? Там циклы и обращение к массиву. Больше ничего нету. Мне просто лень переводить на C, бо как сама задача решена.
Вот приведенный выше код, переписанная на С (ну, загрузку в массив сам напишешь, там просто...):
Код:
// Array and size, should be updated during input data loading
int A[][]; // Array
int n = 0; // Size of an array

void DeleteIsland(int ai, aj)
{
  A[i][j] = 0;
  for (int i = ai-1; i <= ai+1; ++i)
    for (int j = aj-1; j < aj+1; ++j)
      if (i >=0 && i < n && j >= 0 && j < n)
        if (A[i],[j] == 1)
          DeleteIsland(i,j);
}

int CountIslands()
{
  int Result = 0;

  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (A[i][j] == 1)
      {
        Result++;
        DeleteIsland(i,j);
      }

  return Result;
}

Последний раз редактировалось lmikle, 30.07.2015 в 00:12.
Ответить с цитированием
Этот пользователь сказал Спасибо lmikle за это полезное сообщение:
Luster (30.07.2015)
  #6  
Старый 30.07.2015, 00:09
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

То же самое, только на си, чуть правильней (диагонали не должны учитываться по заданию) и с немного меньшим числом проверок во время выполнения, хотя выглядит корявее:
Код:
void deleteIsland(char **map, int x, y)
{
    if (map[y][x] == 0)
        return;
    map[y][x] = 0;
    if (y > 0)
        deleteIsland(map, x, y-1);
    if (y < n-1)
        deleteIsland(map, x, y+1);
    if (x > 0)
        deleteIsland(map, x-1, y);
    if (x < n-1)
        deleteIsland(map, x+1, y);
}

int islandsCount(char **map, int N)
{
    int result = 0;
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x)
            if (map[y][x] != 0)
            {
                ++result;
                deleteIsland(map, x, y);
            }
    return result;
}
__________________
jmp $ ; Happy End!
The Cake Is A Lie.
Ответить с цитированием
Этот пользователь сказал Спасибо Bargest за это полезное сообщение:
Luster (30.07.2015)
  #7  
Старый 30.07.2015, 00:16
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 7,788
Версия Delphi: 7, XE3, 10.2
Репутация: 49089
По умолчанию

Bargest, да, про диагонали ты прав. Что-то поленился я
Вообще, надо подумать как можно такой паттерн проверки написать красиво... Двумя циклами?..
Код:
int i;
for (i=x-1; i<x+2; ++i) deleteIsland(map,i,y);
for (i=y-1; i<y+2; ++i) deleteIsland(map,x,i);
Все-равно не красиво
Да и 2 лишнии итерации, которые совсем ни к селу. ни к городу...

ЗЫ. if'ы специально сейчас пропустил...

Последний раз редактировалось lmikle, 30.07.2015 в 00:20.
Ответить с цитированием
  #8  
Старый 30.07.2015, 00:23
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

Я думал - ничего толком не придумал. Либо выходит кривой и медленный обход в ширину, либо рекурсия и обход в глубину. Фактически это поиск компонент связности графа, и та же вика предлагает обычный поиск в ширину и глубину.

Касаемо самой проверки, можно как и сказано в "решении" - добавить лишние столбцы и ячейки с нулями, тогда ифы можно вообще выпилить. Получится просто 4 вызова делета. Можно в цикл свернуть по 2:
Код:
for (int i = -1; i < 2; i += 2)
{
    deleteIsland(map,x+i,y);
    deleteIsland(map,x,y+i)
}
но как-то это тупо.
__________________
jmp $ ; Happy End!
The Cake Is A Lie.

Последний раз редактировалось Bargest, 30.07.2015 в 22:34.
Ответить с цитированием
  #9  
Старый 30.07.2015, 00:51
Luster Luster вне форума
Прохожий
 
Регистрация: 29.07.2015
Сообщения: 5
Версия Delphi: visual studio
Репутация: 10
По умолчанию

Большое спасибо, как я понял мне осталось: загрузить через файл массив и размерность, записать результат в файл. И еще вопросик: данный алгоритм реализуется с помощью обхода именно в глубину?
Ответить с цитированием
  #10  
Старый 30.07.2015, 04:50
lmikle lmikle вне форума
Модератор
 
Регистрация: 17.04.2008
Сообщения: 7,788
Версия Delphi: 7, XE3, 10.2
Репутация: 49089
По умолчанию

В общем, да. Просто он локальный.
Точнее так.
Общий обход - фактически в ширину (проверяем все клетки по очереди). При нахождении острова делаем локальный обход в глубину.
Ответить с цитированием
  #11  
Старый 30.07.2015, 22:38
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

На тему шаблона проверок - вот еще немного бредовая свертка
Код:
for (int i = 0; i < 4; ++i)
    deleteIsland(map, x - 1 + ((i & 1) << 1), y - 1 + (i & 2));

А по теме - ну да, зачитать файл циклом через fscanf или ifstream, записать еще проще.
__________________
jmp $ ; Happy End!
The Cake Is A Lie.
Ответить с цитированием
  #12  
Старый 31.07.2015, 16:19
Luster Luster вне форума
Прохожий
 
Регистрация: 29.07.2015
Сообщения: 5
Версия Delphi: visual studio
Репутация: 10
По умолчанию

Доброе время суток. Вот собрал код. Но матрица выводится с 0, а нужно с 1, если size -\+ 1 то в строках проходит, а в столбцах ошибка. Так же результат как только не пробовал записать в файл - ошибка. И взгляните пожалуйста на функции удаления и поиска. Правильно ли я все сделал?

Код:
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <windows.h>
using namespace std;
int size;
int result;
int  main(void) 
{
	setlocale(LC_ALL,"RUS");
     int  r, c;
     FILE* fp = fopen("1.txt", "r"); 
     if(! fp)
         exit(1);
     fscanf(fp, "%2d", &size); 
     fgetc(fp);
     if(! size)
	  {
           fclose(fp);
           exit(2);
      }
    
      int** mat  = new int*[size];
      for(r = 0; r < size; r++)
            mat[r] = new int[size];
 
      char  buf[255];
      char* str;
 
      memset(buf, '\0', sizeof(buf));
      for(r = 0; fgets(buf, sizeof(buf), fp); r++) 
      
	
{ 
               for(c = 0, str = strtok(buf, " "); str; str = strtok(NULL, " "), c++)
                     mat[r][c] = atoi(str);
                 }
                 fclose(fp);
                     std::cout << "\n\nÑìåæíàÿ ìàòðèöà ðåçóëüòàòà:\n";
	std::cout << "    |"; for ( r = 0; r<size; r++) printf(" %3d", r);
	std::cout << "\n----+";
	for ( r = 0; r<size; r++) std::cout << "----";
	std::cout << '\n';
	for ( r = 0; r<size; r++) 
	{        
		printf("%3d |", r);
		for (c = 0; c<size; c++) printf(" %3d", mat[r][c]);
		std::cout << "\n";
		
	}
	int islandsCount();
	void deleteIsland();
	
	

ofstream f;
f.open("filename");
f << result;
f.close();
	

void deleteIsland(char **mat, int r, int c)
{
    if (mat[r][c] == 0)
        return;
    mat[r][c] = 0;
    if (r > 0)
        deleteIsland(mat, r, c-1);
    if (c < size-1)
        deleteIsland(mat, r, c+1);
    if (r > 0)
        deleteIsland(mat, r-1, c);
    if (r < size-1)
        deleteIsland(mat, r+1, c);
}
 
int islandsCount(char **mat, int size)
{
    for (int c = 0; c < size; ++c)
        for (int r = 0; r < size; ++r)
            if (mat[c][r] != 0)
            {
                ++result;
                deleteIsland(mat, r, c);
            }
    return result;
    
}

lmikle: пользуемся тегами оформления, иначе придут санкции и запинают моск...

Последний раз редактировалось lmikle, 31.07.2015 в 18:47.
Ответить с цитированием
  #13  
Старый 01.08.2015, 12:49
Аватар для Bargest
Bargest Bargest вне форума
Профессионал
 
Регистрация: 19.10.2010
Адрес: Москва
Сообщения: 2,390
Версия Delphi: XE3/VS12/FASM
Репутация: 14665
По умолчанию

Это вообще не код. Функции нельзя объявлять в функциях, функция поиска ни разу не вызывается, фигурные скобки main-а не закрыты, mat сделан int-ами, в то время как в функции используется char. Это в принципе не может скомпилироваться вообще никаким местом. Не говоря уже об ошибках и опечатках, допущенных при замене X и Y на R и C соответственно (зачем вообще это было делать?).
Вот примерно рабочий код, восстановленный из этого.
Цитата:
#include <stdio.h>
#include <Windows.h>

void deleteIsland(char **mat, int r, int c, int msize)
{
if (mat[c][r] == 0)
return;
mat[c][r] = 0;
if (c > 0)
deleteIsland(mat, r, c - 1, msize);
if (c < msize - 1)
deleteIsland(mat, r, c + 1, msize);
if (r > 0)
deleteIsland(mat, r - 1, c, msize);
if (r < msize - 1)
deleteIsland(mat, r + 1, c, msize);
}

int islandsCount(char **mat, int size)
{
int result = 0;
for (int c = 0; c < size; ++c)
for (int r = 0; r < size; ++r)
if (mat[c][r] != 0)
{
++result;
deleteIsland(mat, r, c, size);
}
return result;

}
int main(void)
{
int msize = 0;
int r, c;
FILE* fp = fopen("1.txt", "r");
if (!fp)
return 1;
fscanf(fp, "%2d", &msize);
fgetc(fp);
if (!msize)
{
fclose(fp);
return 2;
}

char** mat = new char*[msize];
for (r = 0; r < msize; r++)
mat[r] = new char[msize];

char buf[255];
char* str;

memset(buf, '\0', sizeof(buf));
for (r = 0; fgets(buf, sizeof(buf), fp); r++)
{
for (c = 0, str = strtok(buf, " "); str; str = strtok(NULL, " "), c++)
mat[r][c] = atoi(str);
}
fclose(fp);
printf("%i", islandsCount(mat, msize));
return 0;
}
Пишет ответ в консоль. В файл сам уж переделаешь.

ЗЫЖ модераторам: специально quote поставил, т.к. подсветка C++ кода как делфы, где половина кода расцвечивается рандомом, а другая половина уходит в комментарий - это кошмар... Лучше уж без отступов, чем с этим трешем.
__________________
jmp $ ; Happy End!
The Cake Is A Lie.

Последний раз редактировалось Bargest, 01.08.2015 в 12:54.
Ответить с цитированием
Этот пользователь сказал Спасибо Bargest за это полезное сообщение:
Luster (02.08.2015)
  #14  
Старый 02.08.2015, 23:38
Luster Luster вне форума
Прохожий
 
Регистрация: 29.07.2015
Сообщения: 5
Версия Delphi: visual studio
Репутация: 10
По умолчанию

большое спасибо, очень помогли.
Ответить с цитированием
  #15  
Старый 14.09.2015, 10:37
dreindeimos dreindeimos вне форума
Заблокирован
 
Регистрация: 04.06.2015
Сообщения: 12
Версия Delphi: Delphi 7
Репутация: 10
По умолчанию

Паскаль - и изи переделаешь, только в путь)
Ответить с цитированием
Ответ



Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB-коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Быстрый переход


Часовой пояс GMT +3, время: 01:43.


 

Сайт

Форум

FAQ

RSS лента

Прочее

 

Copyright © Форум "Delphi Sources" by BrokenByte Software, 2004-2021

ВКонтакте   Facebook   Twitter   Ссылка на Telegram