#include <iostream>
#include <fstream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int getInt(char value) {
return ((int) value - (int) '0');
}
char getChar(int value) {
return (char)(value + '0');
}
vector<int> split(const string line, char separator) {
vector<int> result;
for (int i = 0; i < line.length(); ++i) {
if (line[i] != separator) {
result.push_back(getInt(line[i]));
}
}
return result;
}
void fromFile(const char *filename, vector<vector<int>> &R, vector<vector<int>> &D, vector<vector<int>> &directives, int &n, int &m) {
ifstream in(filename);
string line;
if (in.is_open()) {
while (getline(in, line) and line != "Directives") {
n = getInt(line[0]), m = getInt(line[2]);
}
vector<int> temp;
int index = 0;
while (getline(in, line) and line != "R") {
directives.emplace_back(vector<int>());
temp = split(line, ' ');
for (int j = 0; j < temp.size(); ++j) {
directives[index].push_back(temp[j]);
}
index++;
}
index = 0;
while (getline(in, line) and line != "D") {
R.emplace_back(vector<int>());
temp = split(line, ' ');
for (int j = 0; j < temp.size(); ++j) {
R[index].push_back(temp[j]);
}
index++;
}
index = 0;
while (getline(in, line)) {
D.emplace_back(vector<int>());
temp = split(line, ' ');
for (int j = 0; j < temp.size(); ++j) {
D[index].push_back(temp[j]);
}
index++;
}
} else {
cout << "file not found";
}
}
bool Contains(int value, vector<int> vector) {
for (int i = 0; i < vector.size(); ++i) {
if (vector[i] == value) {
return true;
}
}
return false;
}
bool check(int index, int current, vector<char> positions, vector<int> Kr) {
if (index >= 0 && index < positions.size() && positions[index] == '-' && !Contains(index, Kr)) {
return true;
} else {
return false;
}
}
void print(vector<char> vector) {
for (int j = 0; j < vector.size(); ++j) {
cout << vector[j] << " ";
}
cout << endl;
}
void vectorRemove(int value, vector<int> &vector) {
vector.erase(std::remove(vector.begin(), vector.end(), value), vector.end());
}
int calculateLength(vector<vector<int>> R, vector<vector<int>> D) {
int sum = 0;
for (int i = 0; i < R.size(); ++i) {
for (int j = 0; j < R[i].size(); ++j) {
sum += R[i][j] * D[i][j];
}
}
return (int)(sum / 2);
}
vector<vector<int>> swap(vector<vector<int>> R, vector<char> positions) {
vector<vector<int>> result;
for (int i = 0; i < R.size(); ++i) {
result.emplace_back(vector<int>());
for (int j = 0; j < R[i].size(); ++j) {
result[i].push_back(R[getInt(positions[i])][getInt(positions[j])]);
}
}
return result;
}
int main() {
vector<vector<int>> R, D, directives;
vector<int> Ir, Er, Kr;
vector<char> positions;
int n, m, iteration = 0;
char choose;
cout << "Если хотите ввести данные из файла, нажмите 1. В противном случае, будет применен ручной ввод" << endl;
cin >> choose;
if(choose == 'f') {
fromFile("input.txt", R, D, directives, n, m);
} else {
cout << "Введите n" << endl;
cin >> n;
cout << "Введите m" << endl;
cin >> m;
cout << "Введите директивные элементы, чтобыы прекратить ввод директивных элементов, введите f";
}
for (int i = 0; i < R.size(); ++i) {
positions.push_back('-');
Ir.push_back(i);
}
for (int i = 0; i < R.size(); ++i) {
for (int j = 0; j < directives.size(); ++j) {
if (i == (directives[j][1] - 1)) {
positions[i] = getChar(directives[j][0] - 1);
Er.push_back(directives[j][0] - 1);
Ir.erase(std::remove(Ir.begin(), Ir.end(), directives[j][0] - 1), Ir.end());
}
}
}
print(positions);
int index = 0;
do {
iteration++;
for (int i = 0; i < positions.size(); ++i) {
if (positions[i] != '-') {
if (check(i - n, i, positions, Kr)) {
Kr.push_back(i - n);
}
if (i % n != 0) {
if (check(i - 1, i, positions, Kr)) {
Kr.push_back(i - 1);
}
}
if ((i + 1) % n != 0) {
if (check(i + 1, i, positions, Kr)) {
Kr.push_back(i + 1);
}
}
if (check(i + n, i, positions, Kr)) {
Kr.push_back(i + n);
}
}
}
sort(Kr.begin(), Kr.end());
cout << "Шаг " << iteration << endl;
int max = INT_MIN;
for (int i = 0; i < Ir.size(); ++i) {
int Je = 0;
for (int j = 0; j < R.size(); ++j) {
if (R[Ir[i]][j] != 0) {
if (Contains(j, Er)) {
Je += R[Ir[i]][j];
} else {
Je -= R[Ir[i]][j];
}
}
}
cout << "e" << Ir[i] + 1 << ": J = " << Je << endl;
if (Je > max) {
max = Je;
index = Ir[i];
}
}
vector<tuple<int, int>> tempVector;
for (int i = 0; i < Er.size(); ++i) {
if (R[index][Er[i]] != 0) {
int j = 0;
for (j = 0; j < positions.size(); ++j) {
if (positions[j] == getChar(Er[i])) {
break;
}
}
tempVector.emplace_back(tuple(R[index][Er[i]], j));
}
}
int F, min = INT_MAX, position = 0;
for (int i = 0; i < Kr.size(); ++i) {
cout << "В позиции" << Kr[i] + 1 << ": F = ";
F = 0;
for (int j = 0; j < tempVector.size(); ++j) {
F += get<0>(tempVector[j]) * D[Kr[i]][get<1>(tempVector[j])];
}
cout << F << endl;
if (F < min) {
min = F;
position = Kr[i];
}
}
positions[position] = getChar(index);
cout << "Элемент " << index + 1 << " помещен в позицию" << (position + 1) << endl;
vectorRemove(position, Kr);
vectorRemove(index, Ir);
Er.push_back(index);
} while (!Ir.empty());
cout << "Итоговое размещение:" << endl << "L до размещения элементов: " << calculateLength(R, D) << endl;
for (int i = 0; i < positions.size(); ++i) {
cout << getInt(positions[i]) + 1 << "\t";
if ((i + 1) % n == 0) {
cout << endl;
}
}
R = swap(R, positions);
cout << "L после размещения элементов: " << calculateLength(R, D) << endl;
return 0;
}