Помогите решить задачку(что-то в роде олимпиадной).
Матрица(произвольного размера)имитирует воду и остова. Вода представленна как 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;
}
|
Дальше я запутался как гулять по островам считая количество соседних едениц
подскажите пожалуйста:
Оно вроде все просто, проверил есть ли рядом суша, если да перешел на нее, где был затопил(чтоб не мешала), проверил дальше. Но если рядом не один участок суши как пойти одновременно на два и более
участка, или как запомнить это место, а потом на него вернутья? Вобщем что дальше только догадка, которую не могу реализовать.
|
