Pond sizes

16.19 Pond sizes: you have an integer matrix representing a plot of land, where the value at that location represents the height above sea level. a value of zero indicates water. a pond is a region of water connected vertically, horizontally, or diagonally. the size of the pond is the total number of connected water cells. write a method to compute the sizes of all ponds in the matrix.

EXAMPLE
Input:
0 2 1 0
0 1 0 1
1 1 0 1
0 1 0 1

Output: 2, 4, 1 (in any order)

class landUnit {
public:
    landUnit(int d, int x, int y) : data(d), visited(false) {
        loc_x = x;
        loc_y = y;
    }

    int data;
    int visited;
    int loc_x, loc_y;
};

template<size_t inner, size_t outer>
bool isValidUnit(array<array<landUnit*, inner>, outer> &land, int i, int j) {
    return (i >= 0 && i < outer && j >= 0 && j < inner && 
        land[i][j]->visited == false && land[i][j]->data == 0);
}

template<size_t inner, size_t outer>
int breadth_first_search(array<array<landUnit*, inner>, outer> &land, int i, int j) {
    queue<landUnit*> q;

    landUnit* temp = land[i][j];
    temp->visited = true;

    q.push(temp);
    int pondSize = 1;

    while (!q.empty()) {
        j = q.front()->loc_x;
        i = q.front()->loc_y;
        q.pop();
        // vertically, diagonally, or horizontally = pond
        // we must check for the 8 possible locations that
        // surround the pond unit

        // top 3
        for (int k = -1; k < 2; k++) {
            if (isValidUnit(land, i - 1, j + k)) {
                q.push(land[i - 1][j + k]);
                land[i - 1][j + k]->visited = true;
                pondSize++;
            }
        }

        // bottom 3
        for (int k = -1; k < 2; k++) {
            if (isValidUnit(land, i + 1, j + k)) {
                q.push(land[i + 1][j + k]);
                land[i + 1][j + k]->visited = true;
                pondSize++;
            }
        }

        // left and right
        if (isValidUnit(land, i, j - 1)) {
            q.push(land[i][j - 1]);
            land[i][j - 1]->visited = true;
            pondSize++;
        }

        if (isValidUnit(land, i, j + 1)) {
            q.push(land[i][j + 1]);
            land[i][j + 1]->visited = true;
            pondSize++;
        }
    }
    return pondSize;
}

template<size_t inner, size_t outer>
vector<int> pondSizes(array<array<landUnit*, inner>, outer> &land) {
    vector<int> pondSizes;

    // 1) Iterate through matrix
    for (int i = 0; i < land.size(); i++) {
        for (int j = 0; j < land.at(i).size(); j++) {
            // if == 0 and not visited preform breadh first search
            if (land[i][j]->data == 0 && land[i][j]->visited == false) {
                int size = breadth_first_search(land, i, j);
                pondSizes.push_back(size);
            }
        }
    }
    return pondSizes;
}



int main()
{
    //array<array<int, 4>, 4> data =
    //{
    //    {
    //        { 0, 2, 1, 0 },
    //        { 0, 1, 0, 1 },
    //        { 1, 1, 0, 1 },
    //        { 0, 1, 0, 1 }
    //    }
    //};

    array<array<int, 16>, 4> data =
    {
        {
            { 0, 2, 1, 0, 0, 2, 1, 0, 0, 2, 1, 0, 0, 2, 1, 0 },
            { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 },
            { 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1 },
            { 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1 }
        }
    };

    // change before testing
    array<array<landUnit*, 16>, 4> land;

    landUnit *temp;
    for (int i = 0; i < data.size(); i++) {
        for (int j = 0; j < data.at(i).size(); j++) {
            temp = new landUnit(data[i][j], j, i);
            land[i][j] = temp;
        }
    }

    for (int i = 0; i < data.size(); i++) {
        for (int j = 0; j < data.at(i).size(); j++) {
            cout << land[i][j]->data << " ";
        }
        cout << endl;
    }
    cout << endl;
    //pause();

    vector<int> ret = pondSizes(land);
    for (auto i : ret) {
        cout << i << " ";
    }
    cout << endl;
}