Решение задачи по программированию про остров

[HackNick]

Доброго времени суток всем!
Столкнулся с проблемой решения задачи про "остров". Собственно вот сама задача:
Даны размеры поля NxM, которое состоит из "клеток". В каждой клетке может находиться либо суша (тогда значение в клетке будет "1"), либо море ("0"). Нужно найти площадь наибольшего острова. Две клетки суши объядиняются в остров только по вертикали или по горизонтали. Пример:
island.in | island.out
3 3 ----------- 3
1 1 0
1 0 0
0 0 1

Сколько я алгоритмов не придумывал, то и дело на каком нибудь придуманном тесте запорорюсь... Поэтому решил обратиться сюда. Моё последнее решение выглядит так:

#include <stdio.h>
int N, M, maxS=0;
bool island[30][30];

int count(int x, int y, int S) {
    if (island[x][y]) {
        S++;
        if (maxS < S) maxS = S;
        if (x < (N-1)) count(x+1, y, S+ ((y < (M-1)) && (island[x][y+1])) );
        if (y < (M-1)) count(x, y+1, S+ ((x < (N-1)) && (island[x+1][y])) );
        return maxS;
    }
    if (x < (N-1)) count(x+1, y, 0);
    if (y < (M-1)) count(x, y+1, 0);
    return maxS;
}

int main() {
    FILE *f;
    int i, j;
    
    f = fopen("island.in", "r");
    fscanf(f, "%i%i", &N, &M);
    for(j=0;j<M;j++)
    for(i=0;i<N;i++)
        fscanf(f, "%i", &island[i][j]);
    fclose(f);
    
    f = fopen("island.out", "w");
    fprintf(f, "%i", count(0, 0, 0));
    fclose(f);
    return 0;
}

И контрпример против этого решения выглядит так:
3 3
0 1 1
0 1 1
1 1 0

Ответ дает 5...

[sergey.d]

#include <iostream>

const int mw = 10;
const int mh = 10; 

int map[mh][mw] =
{
    { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
    { 0, 1, 0, 0, 0, 0, 1, 1, 0, 1 },
    { 1, 1, 1, 0, 0, 0, 1, 1, 1, 1 },
    { 0, 1, 0, 0, 0, 0, 1, 1, 0, 1 },
    { 0, 0, 0, 1, 1, 1, 0, 0, 0, 1 },
    { 0, 0, 0, 1, 0, 1, 0, 0, 0, 1 },
    { 0, 0, 0, 1, 0, 1, 0, 0, 1, 0 },
    { 0, 0, 0, 1, 0, 1, 0, 0, 1, 0 },
    { 0, 0, 0, 0, 0, 0, 0, 0, 1, 0 },
    { 0, 1, 1, 1, 1, 1, 0, 0, 1, 0 }
};

void island_size(int r, int c, int &sz)
{
    if(map[r][c])
    {
        ++sz;
        map[r][c] = 0;

        if(r - 1 >= 0) island_size(r - 1, c, sz);
        if(r + 1 < mh) island_size(r + 1, c, sz);
        if(c - 1 >= 0) island_size(r, c - 1, sz);
        if(c + 1 < mw) island_size(r, c + 1, sz);
    }
}

int max_island_size()
{
    int sz, max_sz = 0;
    for(int r = 0; r < mh; ++r)
    {
        for(int c = 0; c < mw; ++c)
        {
            sz = 0;
            island_size(r, c, sz);
            if(max_sz < sz) max_sz = sz;
        }
    }

    return max_sz;
}

int main(int argc, char *argv[])
{
    std::cout << "Max. island size: "  << max_island_size() << std::endl;
}

Надеюсь, это поможет