13-14 листопада 2010 року відбудуться заняття обласної школи олімпійського резерву з програмування.
Вітаємо учасників!
Тема 1. Рекурсивні алгоритми.
Задача Кольори "Colours".
На полі, поділеному на клітинки, деякі з них зафарбовані. Визначити кількість зафарбованих зв’язаних областей. З кожної клітинки зв’язаної області можна потрапити до будь-якої іншої її клітинки, змінюючи на кожному кроці лише одну координату на 1. Зафарбована клітинка позначена одиницею, не зафарбована – нулем.
Вхідний файл:
У першому рядку вхідного файлу Colours.dat містяться два числа n та m (0 < n, m < 100) - кількість рядків та стовпців на полі.
Наступні n рядків містять по m чисел, розділених пробілами - кольори клітинок поля. Кожне з чисел - 0 або 1.
Вихідний файл:
У вихідному файлі Colours.sol міститься єдине число - шукана кількість зафарбованих областей.
Приклад вхідних даних:
3 5
1 1 0 1 0
0 0 1 1 1
1 0 1 0 1
Приклад вихідних даних:
3
вариант через волновой алгоритм
ВідповістиВидалити#include
int a[255][255];
int k;
void rec(int i,int j,int n,int m)
{
int is,js,fl;
fl=0;
a[i][j]=2;
while(fl!=m*n)
{
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(a[i][j]!=0)
{
if(a[i-1][j]==2||
a[i+1][j]==2||
a[i][j+1]==2||
a[i][j-1]==2)
{
a[i][j]=2;
}
}
}
}fl++;
}
k=k+1;
}
int main()
ВідповістиВидалити{
ifstream fin("color.dat");
ofstream fout("color.sol");
k=0;
int i,j,n,m,is,js;
fin>>n>>m;
for(i=0;i>a[i][j];
}
}
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
if(a[i][j]==1)
{
rec(i,j,n,m);
}
}
}
fout<<k;
fin.close();
fout.close();
}