5E

#include <iostream>
#include <cstdlib>
#include <fstream>

using namespace std;

void enteringCoordinatesIntoAnArray(ifstream*, int**, int*, int*);
void outputOnDisplay(int**, int*, int*);
void matrixReset(int**, int*, int*);
void enteringCoordinatesIntoAnMatrix(int**, int**, int*, int*);
void maximumSquareSearchAlgorithm(int**, int*, int*, int*, int*, int, int);

int main()
{
    setlocale(LC_ALL, "Russian");
    ifstream in("D:\\Users\\Nevarkir\\source\\repos\\Project1\\Project1\\5e\\input.txt");
    int N; // количество отмеченных точек внутри прямоугольника
    in >> N;
    int W; // ширина прямоугольника
    in >> W;
    W++;
    int H; // высота прямоугольника
    in >> H;
    H++;
    int** M; // массив отмеченных точек внутри прямоугольника
    int G = 2;
    M = new int* [N];
    for (int i = 0; i < N; i++)
    {
        M[i] = new int[G];
    }

    enteringCoordinatesIntoAnArray(&in, M, &N, &G); // заполнение двумерного динамического массива
    // outputOnDisplay(M, &N, &G); // вывод значений двумерного массива в экран
    in.close();

    int** V; // матрица
    // инициализация двумерной динамической матрицы
    V = new int* [H];
    for (int y = 0; y < H; y++)
    {
        V[y] = new int[W];
    }

    matrixReset(V, &H, &W);
    //outputOnDisplay(V, &H, &W);

    enteringCoordinatesIntoAnMatrix(M, V, &N, &H);
    //outputOnDisplay(V, &H, &W);

    int count = 0;
    int max = 0;
    int di = 0;
    int dj = 0;
    int num = 1;
    while (count != ((W * H) - N))
    {
        int F = 1;
        // cout << "============================================================" << endl;
        // cout << "Start - y = " << di << " и x = " << dj << ": длина стороны квадрата = " << F << "; максимальная длина стороные квадрата = " << max << "; отмечено точек = " << count << endl;
        maximumSquareSearchAlgorithm(V, &H, &W, &F, &count, di, dj);
        if (F > max) max = F;
        for (int y = 0; y < H; y++) // подбор следующего индекса с непосещенной вершиной
        {
            for (int x = 0; x < W; x++)
            {
                if (V[y][x] == 0)
                {
                    di = y;
                    dj = x;
                }
            }
        }
        // cout << "End - следующие y = " << di << " и x = " << dj << "; конечные итоги: длина стороны квадрата = " << F << "; максимальная длина стороные квадрата = " << max << "; отмечено точек = "<< count << endl;
    }
    ofstream out;
    out.open("D:\\Users\\Nevarkir\\source\\repos\\Project1\\Project1\\5e\\output.txt");
    //cout << "============================================================" << endl;
    out << max << endl;
    //cout << "============================================================" << endl;
    // outputOnDisplay(V, &H, &W);
    out.close();
    system("PAUSE");
    for (int i = 0; i < N; i++) {
        delete[] M[i];
    }
    delete[] M;
    for (int y = 0; y < H; y++) {
        delete[] V[y];
    }
    delete[] V;
    system("PAUSE");
    return 0;
}

void enteringCoordinatesIntoAnArray(ifstream* in, int** M, int* N, int* G)
{
    for (int i = 0; i < (*N); i++)
    {
        for (int j = 0; j < (*G); j++)
        {
            (*in) >> M[i][j];
        }
    }
}

void outputOnDisplay(int** M, int* N, int*G)
{
    for (int i = 0; i < (*N); i++)
    {
        for (int j = 0; j < (*G); j++)
        {
            cout << M[i][j] << "  ";
        }
        cout << endl;
    }
    cout << "\n" << endl;
}

void matrixReset(int** V, int* H, int* W)
{
    for (int y = 0; y < (*H); y++)
    {
        for (int x = 0; x < (*W); x++)
        {
            V[y][x] = 0;
        }
    }
}

void enteringCoordinatesIntoAnMatrix(int** M, int** V, int* N, int* H)
{
    for (int i = 0; i < (*N); i++)
    {
        V[(*H) - 1 - M[i][1]][M[i][0]] = 1;
    }
}

void maximumSquareSearchAlgorithm(int** V, int* H, int* W, int* F, int* count, int i, int j)
{
    // cout << (*F) << endl;
    if (V[i][j] == 0)
    {
        if (((i + (*F) - 1) < (*H)) && ((j + (*F) - 1) < (*W)))
        {
            int k = 0;
            for (int ki = i; ((ki < (i + (*F))) && (ki < (*H))); ki++)
            {
                for (int kj = j; ((kj < (j + (*F))) && (kj < (*W))); kj++)
                {
                    if (V[ki][kj] != 1)
                    {
                        k++;
                    }
                    // cout << "В точке [y = " << ki << " и x = " << kj << "] со значением " << V[ki][kj] << ", значение k = " << k << ", со значением F = " << (*F) << endl;
                }
            }
            if (k == (*F) * (*F))
            {
                // cout << "Рекурсия!" << endl;
                (*F) = (*F) + 1;
                maximumSquareSearchAlgorithm(V, H, W, F, count, i, j);
            }
            else
            {
                for (int ki = i; ki < (i + (*F) - 1); ki++)
                {
                    for (int kj = j; kj < (j + (*F) - 1); kj++)
                    {
                        if (V[ki][kj] == 0)
                        {
                            (*count)++;
                            V[ki][kj] = 2;
                            (*F) = (*F) - 1;
                        }
                    }
                }
            }
        }
        else
        {
            V[i][j] = 2;
            (*count)++;
            (*F) = (*F) - 1;
        }
    }
}