#include <iostream>
#include <string>
#include <fstream>
#include <vector>

using namespace std;

int inputValue(int min, int max);
pair<int, int> userInputFromConsole();
short** userInputFromFile(string path);
bool checkPath(string path);
string userInputPath();
short inputMethod();
void printInConsole(short** a, short** b);
string userOutputPath();
void printInFile(short** a, short** b, string path);
short outputMethod();
void start();
void printTask();

int inputValue(int min, int max) {
    int currentValue;
    bool isNotValid = true;
    do {
        cin >> currentValue;
        if (currentValue >= min && currentValue <= max)
            isNotValid = false;
        else
            cout << "Введите число в заданном диапазоне\n";
    } while (isNotValid);
    return currentValue;
}

pair<int, int> userInputFromConsole() {
    const int MIN_SIZE = 2;
    const int MAX_SIZE = 100;
    int n, m;
    cout << "Введите размерность матрицы в диапазоне " << MIN_SIZE << ".." << MAX_SIZE << ": ";
    n = inputValue(MIN_SIZE, MAX_SIZE);
    m = inputValue(MIN_SIZE, MAX_SIZE);
    return make_pair(n, m);
}

short** userInputMatrixFromConsole(pair<int, int> size) {
    const int MIN_VALUE = 0;
    const int MAX_VALUE = 1;
    int n = size.first;
    int m = size.second;
    cout << "Введите элементы матрицы в диапазоне " << MIN_VALUE << ".." << MAX_VALUE << ": " << endl;
    short** matrix = new short* [n];
    for (int i = 0; i < n; i++) {
        matrix[i] = new short[m];
        for (int j = 0; j < m; j++)
            matrix[i][j] = inputValue(MIN_VALUE, MAX_VALUE);
    }
    return matrix;
}

short** userInputFromFile(string path) {
    int n, m;
    ifstream file(path);
    file.open(path);
    file.clear();
    file >> n;
    file >> m;
    short** matrix = new short*[n];
    for (int i = 0; i < n; i++) {
        matrix[i] = new short[m];
        for (int j = 0; j < m; j++)
            file >> matrix[i][j];
    }
    file.close();
    return matrix;
}

bool checkPath(string path) {
    ifstream file(path);
    if (file.is_open()) {
        cout << path << " найден" << endl;
        return true;
    }
    else {
        cout << path << " не найден" << endl;
        return false;
    }
}

string userInputPath() {
    string path;
    bool isNotValid = false;
    do {
        cout << "Введите абсолютный путь к файлу с входными данными" << endl;
        cin >> path;
    } while (!checkPath(path));
    return path;
}

short inputMethod() {
    short method;
    cout << "Каким способом хотите ввести данные?" << endl;
    cout << "1 - с помощью консоли" << endl;
    cout << "2 - с помощью файла" << endl;
    do {
        cin >> method;
        if (method != 1 && method != 2)
            cout << "Введите 1 или 2" << endl;
    } while (method != 2 && method != 1);
    return method;
}

void printInConsole(short** a, short** b) {
    cout << "Исходная матрица" << endl;
    for (int i = 0; i < _msize(a) / sizeof(a); i++) {
        for (int j = 0; j < _msize(a[0]) / sizeof(a[0][0]); j++)
            cout << a[i][j] << " ";
        cout << endl;
    }
    cout << endl;
    cout << "Найденная подматрица" << endl;
    for (int i = 0; i < _msize(a) / sizeof(a); i++) {
        for (int j = 0; j < _msize(a[0]) / sizeof(a[0][0]); j++)
            cout << b[i][j] << " ";
        cout << endl;
    }
}

string userOutputPath() {
    string path;
    cout << "Введите абсолютный путь к файлу для вывода результата" << endl;
    cin >> path;
    return path;
}

void printInFile(short** a, short** b, string path) {
    ofstream file(path);
    for (int i = 0; i < _msize(a) / sizeof(a); i++) {
        for (int j = 0; j < _msize(a[0]) / sizeof(a[0][0]); j++)
            file << a[i][j] << " ";
        file << endl;
    }
    file << endl;
    for (int i = 0; i < _msize(a) / sizeof(a); i++) {
        for (int j = 0; j < _msize(a[0]) / sizeof(a[0][0]); j++)
            file << b[i][j] << " ";
        file << endl;
    }
    cout << "Результат работа помещён в файл";
}

short outputMethod() {
    short method;
    cout << "Куда хотите вывести результат?" << endl;
    cout << "1 - в консоль" << endl;
    cout << "2 - в файл" << endl;
    do {
        cin >> method;
        if (method != 1 && method != 2)
            cout << "Введите 1 или 2" << endl;
    } while (method != 2 && method != 1);
    return method;
}

short** userInput() {
    pair<int, int> size;
    short** matrix;
    short method = inputMethod();
    if (method == 1) {
        size = userInputFromConsole();
        matrix = userInputMatrixFromConsole(size);
    }
    else {
        string path = userInputPath();
        matrix = userInputFromFile(path);
    }
    return matrix;
}

void printResult(short** a, short** b) {
    short method = outputMethod();
    if (method == 1)
        printInConsole(a, b);
    else {
        string path = userOutputPath();
        printInFile(a, b, path);
    }
}

short** findMatrix(short** matrix) {
    int n = _msize(matrix) / sizeof(matrix);
    int m = _msize(matrix[0]) / sizeof(matrix[0][0]);
    short** b = new short* [_msize(matrix) / sizeof(matrix)];
    for (int i = 0; i < _msize(b) / sizeof(b); i++) {
        b[i] = new short[_msize(matrix[0]) / sizeof(matrix[0][0])];
        for (int j = 0; j < _msize(matrix[0]) / sizeof(matrix[0][0]); j++)
            b[i][j] = 0;
    }
    vector<int> a, x1, x2, y1, y2;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (matrix[i][j] == 1) {
                int dlin = 0;
                int minShir = 0;
                int c = i;
                int k = j;
                while (matrix[c][k] == 1) {
                    int shir = 0;
                    while (matrix[c][k] == 1) {
                        k++;
                        shir++;
                        if (minShir != 0)
                            if (shir > minShir) {
                                shir--;
                                break;
                            }
                        if (k == m) {
                            k--;
                            break;
                        }
                    }
                    if (minShir > shir || minShir == 0)
                        minShir = shir;
                    dlin++;
                    a.push_back(dlin * minShir);
                    x1.push_back(i);
                    x2.push_back(c);
                    y1.push_back(j);
                    y2.push_back(y1[y1.size() - 1] + minShir - 1);
                    k = j;
                    c++;
                    if (c == n) {
                        c--;
                        break;
                    }
                }
            }

    int maxId = 0;
    for (int i = 0; i < a.size(); i++)
        if (a[i] > a[maxId])
            maxId = i;
    for (int i = x1[maxId]; i < x2[maxId] + 1; i++)
        for (int j = y1[maxId]; j < y2[maxId] + 1; j++)
            b[i][j] = 1;
    return b;
}

void printTask() {
    cout << "Данная программа находит максимальную подматрицу из единиц" << endl;
}

void start() {
    printTask();
    short** matrix = userInput();
    short** newMatrix = findMatrix(matrix);
    printResult(matrix, newMatrix);
}

int main()
{
    setlocale(LC_ALL, "Russian");
    start();
}