#include <iostream>
#include <vector>
#include <windows.h>
#include "matrix.h"

using namespace std;

typedef vector<int> Function;
typedef vector<vector<int>> FunctionFull;

FunctionFull Assignation(int ** data, int N, int M, Function Choice, Function BusyPos, FunctionFull Opt, int j) {

	for (int i = 0; i < M; i++) {
		if(BusyPos[i] == 0) {
			BusyPos[i] = 1;
			Choice[j] = i;
			Choice[N] += data[Choice[j]][j];
			if (j < N-1) Opt = Assignation(data, N, M, Choice, BusyPos, Opt, j+1);
			if(Choice[N] >= Opt[0][N]) {
				if(Choice[N] > Opt[0][N]) Opt.clear();
				Opt.push_back(Choice);
				Choice[N] -= data[Choice[j]][j];
			}
			else {
				BusyPos[i] = 0;
				Choice[N] -= data[Choice[j]][j];
			}
		}
	}
	
	return Opt;
}
 
FunctionFull Assignation(int ** data, int N, int M) {
	return Assignation(data, N, M, Function(N+1, 0), Function(N+1, 0), FunctionFull(1,Function(N+1, 0)), 0);
}
FunctionFull Assignation1(int ** data, int N, int M, Function Choice, Function BusyPos, FunctionFull Opt, int j) {

	for (int i = 0; i < N; i++) {
		if(BusyPos[i] == 0) {
			BusyPos[i] = 1;
			Choice[j] = i;
			Choice[N] += data[Choice[j]][j];
			if (j < N-1) Opt = Assignation(data, N, M, Choice, BusyPos, Opt, j+1);
			if(Choice[N] >= Opt[0][N]) {
				if(Choice[N] > Opt[0][N]) Opt.clear();
				Opt.push_back(Choice);
				Choice[N] -= data[Choice[j]][j];
			}
			else {
				BusyPos[i] = 0;
				Choice[N] -= data[Choice[j]][j];
			}
		}
	}
	
	return Opt;
}
 
FunctionFull Assignation1(int ** data, int N, int M) {
	return Assignation1(data, N, M, Function(N+1, 0), Function(N+1, 0), FunctionFull(1,Function(N+1, 0)), 0);
}


void Result(FunctionFull Optimal){
	for (auto v : Optimal) {
		for(int i : v) cout << i << ' ';
	cout << endl;
	}
}

int main() {
	
	SetConsoleCP (1251);
	SetConsoleOutputCP (1251);
    
	int N, M;
	cout << "Введите размер матрицы MxN (Сотрудников х Должностей): ";
	cin >> N >> M;
	
	if(M <= 1 && N <= 1){
		cerr << "Сотрудников / Дожностей должно быть больше одного!";
		return -2;
	}
	
	int size = N * M;

	int ** data = new int * [size];
	for (int j = 0; j < size; j++) {
		data [j] = new int [size]; 
	}

	int Option;
	cout << "Сгенерировать матрицу (0) или вводить самостоятельно (...)?" << endl;
	cin >> Option;
	system("cls");
	
	if(Option){
		cout << "Введите данные о " << size << " сотрудниках: " << endl;
		Input(data, N, M, Option);
		system("cls");
		cout << "Введенная матрица (" << M  << "x" << N << "):"  << endl;
		OutPut(data, N, M);
	}else{
		Input(data, N, M, Option);
		cout << "Сгенерированная матрица(" << M  << "x" << N << "):"  << endl;
		OutPut(data, N, M);
	}
	
	if (N <= M){
		FunctionFull Optimal = Assignation(data, N, M);
		cout << endl;
		cout << "Результат выбора сотрудников (Номер i сотрудника на должности j): " << endl;
		Result(Optimal);
		} else{
			int ** copy = new int * [size];
			for (int j = 0; j < size; j++) {
				copy [j] = new int [size]; 
			}
			Transpose(copy, data, N, M);
			FunctionFull Optimal = Assignation1(copy, N, M);	
			cout << "Результат выбора сотрудников (Номер j сотрудника на должности i): " << endl;
			Result(Optimal);
		}		
	return 0;
}