VPF::Нахождение островов - Форум программистов

reddevil

Дата 26.9.2005, 15:12 (ссылка)

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

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 38
Регистрация: 27.6.2005
Где: Украина. г.Днепро петровск

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

Помогите решить задачку(что-то в роде олимпиадной).
Матрица(произвольного размера)имитирует воду и остова. Вода представленна как 0, а остров как 1.
Островом считается набор близлежащих единиц.
Необходимо: написать прогу, которая:
1. Считает количество островов
2. Размер каждого острова
3. Координаты острова
4. сохраняет данные в структуре

Я решил сначало описать структуру остров

Код


struct Island{        // Координаты острова
    int x;
    int y;
};

struct Land{
    Island *coord;    // Массив координат
    int size;    // Размер острова
};

Затем объявил глобаьно(чтоб не перекидывать из функции в функцию):
1. массив воды и островов(map)
2. размер карты
3. массив соседних координат на карте
4. количество островов

Код


int **map;                                //Глобальные данные
const int size=20;
int offstep[8][2];
int count;

Иницализировал карту островами и обеспечил вывод на консоль
вот вобщем весь код(не весь, в остальном я сам запутался, не хочу путать других)

Функции void Skan_Map(Land*); и Land *Add_Island(Land*island,int x,int y); не работают, поставил в качестве примера.

Код


#include "stdafx.h"

using namespace std;

//**********************************
struct Island{
    int x;
    int y;
};

struct Land{
    Island *coord;
    int size;
};
//*********************************

int **map;                                //Глобальные данные
const int size=20;
int offstep[8][2];
int count=0;

//_______________________________________Вывод массива на консоль
void Print_Map()
{
    for(int i=0;i<size;i++){
        for(int n=0;n<size;n++)
            cout<<map[i][n]<<" ";
        cout<<endl;
    }
}

//_______________________________________Заполнение карты островами
void Init_Map()
{
    map[0][0]=1;    map[1][0]=1;    map[0][1]=1;
    map[19][19]=1;    map[18][19]=1;    map[19][18]=1;
    map[19][0]=1;    map[18][0]=1;    map[19][1]=1;
    map[0][19]=1;    map[0][18]=1;    map[1][19]=1;
    map[9][9]=1;    map[9][10]=1;    map[10][9]=1;    map[10][10]=1;
}

void Skan_Map(Land*);
Land *Add_Island(Land*island,int x,int y);

int _tmain(int argc, _TCHAR* argv[])
{
    map=new int*[size];
    for(int i=0;i<size;i++){
        map[i]=new int[size];
        for(int n=0;n<size;n++)
            map[i][n]=0;                // Заполнение массива нулями
    }
    
    Land *island=0;

    offstep[0][0]=-1;    offstep[0][1]=-1;    // Направления движения
    offstep[1][0]=0;    offstep[1][1]=-1;
    offstep[2][0]=1;    offstep[2][1]=-1;
    offstep[3][0]=1;    offstep[3][1]=0;
    offstep[4][0]=1;    offstep[4][1]=1;
    offstep[5][0]=0;    offstep[5][1]=1;
    offstep[6][0]=-1;    offstep[6][1]=1;
    offstep[7][0]=-1;    offstep[7][1]=0;

    Init_Map();
    Print_Map();
// Здесь функция Skan_Map(island);

    for(int i=0;i<size;i++)                // Освобождение памяти
        delete[]map[i];
    delete[]map;

    return 0;
}

void Skan_Map(Land*island)
{
// Тут тоже ясно, for x и y<size x и y ++  
    if(array[x][y])
        island=Add_Island(island,x,y);

}

Land *Add_Island(Land*island,int x,int y)
{
    Land*temp;
    if(!count){            // Если первый остров
        temp=new*Land[count+1];
        temp[count].size=1;
        temp[count].coord=new*Island[temp[count].size];
        temp[count].coord[temp[count].size-1].x=x;
        temp[count].coord[temp[count].size-1].y=y;
        count++;
        return temp;
    }

Дальше я запутался как гулять по островам считая количество соседних едениц
подскажите пожалуйста:
Оно вроде все просто, проверил есть ли рядом суша, если да перешел на нее, где был затопил(чтоб не мешала), проверил дальше. Но если рядом не один участок суши как пойти одновременно на два и более
участка, или как запомнить это место, а потом на него вернутья? Вобщем что дальше только догадка, которую не могу реализовать.

maxim1000

Дата 26.9.2005, 21:27 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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

еще один вариант, несколько быстрее, как мне кажется:
тут вообще нужен только один проход smile

смотрим ан первую строку, она состоит из отрезков суши и воды по очереди
каждый отдельный отрезок суши называем отстровом, даем ему номер, можно объект какой-нибудь для него создать - неважно
переходим на следующую строку и смотрим...
какие варианты могут быть:
1. остров тупо продолжается (в общем-то ничего особенного не делаем)
2. остров заканчивается (сохраняем его в массиве "готовых" островов)
3. два острова (или больше) объединяются (один удалить, другой оставить)
4. начинаестя новый (создать новый объект/выделить новый номер)

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

qqq

maxim1000

Дата 26.9.2005, 22:25 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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

попробовал изобразить это в C++
предположение1:имеется класс CIsland с конструктором CIsland(int x,int y)
предположение2:вехняя строчка и левый столбец - все в воде (просто для удобства)

на вход дается массив, куда записываются найденные острова
возвращается количество...

Код


class CIsland
{
  public:
    CIsland(int x,int y);
  ...
};

const int xsize=100;
const int ysize=100;
int IslandsSearch(CIsland *array,bool **map)
{
  int x,y;
  int count=0;//считает острова
  int Indices[xsize];//сопоставляет каждой точке номер острова (-1 - вода)
  for(x=0;x<xsize;x++)
    Indices[x]=-1;//на первой строчке нету островов
  for(y=1;y<ysize;y++)
  {
    int NewIndices[xsize];//новые номера для новой строчки
    for(x=1;x<xsize;++x)
      if(!map[x][y])//вода
        NewIndices[x]=-1;
      else//земля
      {
        if(NewIndices[x-1]<0)//слева острова нету
        {
          if(Indices[x]<0)//и сверху острова нету, значит, новый остров
          {
            NewIndices[x]=count;
            array[count++]=new CIsland(x,y);
          }
          else//это - просто продолжение верхнего острова
            NewIndices[x]=Indices[x];
        }
        else//слева есть остров
        {
          if(Indices[x]<0)//сверху нету - просто продолжаем остров
            NewIndices[x]=NewIndices[x-1];
          else//сверху тоже есть, проверяем, это тот же самый или нет
          {
            NewIndices[x]=Indices[x];//так или иначе, индекс такой же
            if(NewIndices[x-1]!=Indices[x])//оказывается, тут соединяются два острова
            {
              //удалить один из них (например, верхний)
              delete array[Indices[x]];
              count--;
              //...а все его точки назначить левому
              for(int temp=1;temp<xsize;++temp)
                if(NewIndices[temp]==Indices[x])
                  NewIndices[temp]=NewIndices[x];
              //у нас в array получилась "дырка", заполним ее - перенесем туда последний остров
              array[Indices[x]]=array[count-1];
              //и переназначим его точки
              for(temp=1;temp<xsize;++temp)
                if(NewIndices[temp]==count-1)
                  NewIndices[temp]=Indices[x];
              //ну и уменьшим количество островов
              --count;
            }
          }
        }
      }
    for(x=0;x<xsize;++x)//теперь эта строчка становится предыдущей
      Indices[x]=NewIndices[x];
  }
  return count;
}

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

qqq

reddevil

Дата 26.9.2005, 23:38 (ссылка)

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

Загрузка ...

Да написано клево, вот только мне опыта не хватает это разобрать, smile

попробую исходить из коментариев, тем более что на первой строке и в первом столбце остров тоже может быть.

P.S: От дополнительных коментариев по этому поводу не откажусь.

maxim1000

Дата 27.9.2005, 12:10 (ссылка)

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

Загрузка ...

Эксперт

Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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

Цитата

на первой строке и в первом столбце остров тоже может быть

просто код оказался короче, если предположить, что их нет
впрочем, это не такое уж натянутое предположение - можно их добавить вручную
иначе нужно будет обрабатывать специальным образом лувый столбец и первую строку - алгоритм не изменится, просто добавится несколько неинтересных строк...

Цитата

P.S: От дополнительных коментариев по этому поводу не откажусь

для того, чтобы прочувствовать этот алгоритм, можно посоветовать вот что:
1. берем лист в клеточку
2. рисуем на нем какие-то острова
3. идем построчно слево направо, сверху вниз
4. пытаемся решить задачу используя только соседние клеточки
5. каждый участок сущи должен быть пронумерован
6. соединенные участки суши должны быть пронумерованы одинаковыми числами (по возможности)
7. если не получается (например, оказывается, что сверху один номер, а слева другой), пишем в клеточку любой из этих двух, а сбоку на листочке пишем что-то типа "5=9", т.е. острова 5 и 9 на самом деле один и тот же

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

qqq

reddevil

Дата 28.9.2005, 08:50 (ссылка)

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

Загрузка ...

Спасибо

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