Инструменты пользователя

Инструменты сайта


reshenie_zadachi_4

Различия

Здесь показаны различия между двумя версиями данной страницы.

Ссылка на это сравнение

reshenie_zadachi_4 [2010/10/16 02:56] (текущий)
Строка 1: Строка 1:
 +====== Задача 4 ======
 +Имеется матрица (n*m) заполненная 1 и 0. Единицы - это острова,​ а нули - море. Если единицы находятся рядом по горизонтали или вертикали - то они образуют один остров. Острова могут быть «гнутыми» и «дырявыми». Найти количество островов.
  
 +<​file>​
 +/* 
 + * File:   ​landcount.cpp
 + * Author: darkfire
 + *
 + * Created on September 24, 2010, 8:45 PM
 + */
 +
 +#include <​stdlib.h>​
 +#include <​iostream>​
 +
 +using std::endl;
 +using std::cin;
 +using std::cout;
 +
 +const int SIZEX=6, SIZEY=6;
 +
 +int endrow(int [][SIZEY], int, int);
 +
 +int main() {
 +    int ar[SIZEX][SIZEY];​
 +    int countland = 0;
 +    //​заполнение массива ar
 +    for (int x=0;​x<​SIZEX-1;​x++)
 +    {
 +        cout<<"​\n";​
 +        for (int y=0;​y<​SIZEY-1;​y++){
 +            ar[x][y] = rand()%2;
 +            cout<<​ar[x][y]<<"​\t";​
 +        }
 +    }
 +    cout<<"​\n\n";​
 +    //​поиск островов
 +    for (int x=0;​x<​SIZEX-1;​x++){
 +        cout<<"​\n";​
 +        for (int y=0;​y<​SIZEY-1;​y++){
 +            if (ar[x][y] ==1){
 +                countland++;​
 +                endrow(ar,​x,​y);​
 +            }
 +        }
 +    }
 +    //​вывод массива после поиска
 +        cout<<"​\n\n";​
 +    for (int x=0;​x<​SIZEX-1;​x++){
 +        cout<<"​\n";​
 +        for (int y=0;​y<​SIZEY-1;​y++){
 +            cout<<​ar[x][y]<<"​\t";​
 +        }
 +    }
 +        cout<<"​\n"<<"​Kol-vo land: "<<​countland<<​endl;​
 +        return (EXIT_SUCCESS);​
 +}
 +
 +int endrow(int arrb[][SIZEY],​ int x, int y)
 +{
 +    arrb[x][y]=3;//​пометили,​ что часть острова найдена
 +    //​исследуем вправо и вниз от помеченной точки, рекурсивно вызывая функцию endrow
 +    if (arrb[x][y+1]==1){
 +        endrow(arrb,​x,​y+1);​
 +    };
 +        if (arrb[x+1][y]==1){
 +        endrow(arrb,​x+1,​y);​
 +    };
 +}
 +</​file>​
reshenie_zadachi_4.txt · Последние изменения: 2010/10/16 02:56 (внешнее изменение)