sottomat.cpp

#include <fstream>
#include <iostream>
#include <cmath>
#include <climits>
#include <vector>

using namespace std;


enum DIR {
	UP,
	DOWN,
	LEFT,
	RIGHT
};

int readRow(int y, int startX, int endX);
int findsottomat();
void readArray();
int changeSize(int step, DIR direction);
int readMatrix(int startX, int startY, int endX, int endY);
bool grow(int step);
bool checkLimits(int step, DIR direction);
bool decrease(int step);
void printMatrix();

struct movement {
	DIR direction;
	int value;
};

struct point {
	int value;
	int x;
	int y;
};

struct sottomat {
	int startX;
	int startY;
	int endX;
	int endY;
	int value;
} matrix;

struct point start;
enum DIR directions[] = {UP, DOWN, LEFT, RIGHT};

int array[2000][2000];
int rows = 0;
int columns = 0;

ifstream in("input.txt");
ofstream out("output.txt");

int main() {	
	readArray();
	cout << "Result: " << findsottomat() << endl;

	return 0;
}

void initMatrix() {
	matrix.value = start.value;
	matrix.startX = start.x;
	matrix.startY = start.y;
	matrix.endX = start.x;
	matrix.endY = start.y;
	cout << "startValue=" << start.value << " x=" << start.x << " y=" << start.y << endl;
}

int findsottomat() {
	bool stopGrow = false;
	bool stopDecrease = false;
	initMatrix();
	int growStep = 1;
	int decreaseStep = -1;
	int count = 0;

	while (!stopGrow  || !stopDecrease) {
	
		if (grow(growStep)) {
			growStep = 1;
			decreaseStep = -1;
			stopDecrease = false;
		} else {
			growStep++;
			stopGrow = true;
		}

		if (decrease(decreaseStep)) {
			growStep = 1;
			decreaseStep = -1;
			stopGrow = false;
		} else {
			decreaseStep--;
			stopDecrease = true;
			
		}

		printMatrix();

	}

	cout << endl << "END:";
	printMatrix();	
	return matrix.value;
}

bool grow(int step) {
	bool changed = false;
	
	vector<movement> moves;
	
	for (int i = 0; i < 4; i++) {
	
		enum DIR direction = directions[i];
		if (checkLimits(step, direction)) {
			struct movement move;
			move.value = changeSize(step, direction);
			move.direction = direction;
			moves.push_back(move);
		}
	}
	
	if (moves.empty()) {
		return false;
	}
	
	movement maxMove;
	maxMove.value = INT_MIN;
	
	for (movement& move: moves) {
		if (move.value >= maxMove.value) {
			maxMove.value = move.value;
			maxMove.direction = move.direction;
		}
	}

	if (maxMove.value >= 0) {
		matrix.value += maxMove.value;
		switch (maxMove.direction) {
			case UP: 
				matrix.startY -= step;
				break;
			case DOWN:
				matrix.endY += step;
				break;
			case RIGHT:
				matrix.endX += step;
				break;
			case LEFT:
				matrix.startX -= step;
		}
		changed = true;
	}
	return changed;
}

bool decrease(int step) {
	//cout << "decrease, " <<"step: " << step << endl;
	//printMatrix();
	bool changed = false;
	
	vector<movement> moves;
	
	for (int i = 0; i < 4; i++) {
	
		enum DIR direction = directions[i];
		if (checkLimits(step, direction)) {
			struct movement move;
			move.value = changeSize(step, direction);
			move.direction = direction;
			moves.push_back(move);
		}
	}
	
	if (moves.empty()) {
		return false;
	}
	movement maxMove;
	maxMove.value = INT_MAX;
	
	for (movement& move: moves) {
		if (move.value < maxMove.value) {
			maxMove.value = move.value;
			maxMove.direction = move.direction;
		}
	}

	if (maxMove.value < 0) {
		matrix.value -= maxMove.value;
		switch (maxMove.direction) {
			case UP: 
				matrix.startY += step;
				break;
			case DOWN:
				matrix.endY -= step;
				break;
			case RIGHT:
				matrix.endX -= step;
				break;
			case LEFT:
				matrix.startX += step;
		}
		changed = true;
	}
	return changed;
}

bool checkLimits(int step, DIR direction) {
	bool checked = true;
	switch (direction) {
	case UP:	
		if (matrix.startY - step < 0 || 			matrix.startY - step >= matrix.endY) {
			checked = false;
		}
		break;
	case DOWN:
		if (matrix.endY + step >= rows ||			matrix.endY + step <= matrix.startY) 
			checked = false;
		break;
	case RIGHT:
		if (matrix.endX + step >= columns ||	matrix.endX + step <= matrix.startX) 
			checked = false;
		break;		
	case LEFT:
		if (matrix.startX - step < 0 || 			matrix.startX - step >= matrix.endX) 
			checked = false;
		break;
	}
	
	return checked;
}

int changeSize(int step, DIR direction) {
	int change = 0;
	
	switch (direction) {
	case UP:	
		if (step > 0)
				change+= readMatrix(matrix.startX, matrix.startY - step, matrix.endX, matrix.startY - 1);
			else {
				change+= readMatrix(matrix.startX, matrix.startY, matrix.endX, matrix.startY - step - 1);	
			}
		break;
	case DOWN:	
		if (step > 0)
				change+= readMatrix(matrix.startX, matrix.endY + 1, matrix.endX, matrix.endY + step);
			else
				change+= readMatrix(matrix.startX, matrix.endY + step + 1, matrix.endX, matrix.endY);	
		break;
	case LEFT:	
		if (step > 0)
				change+= readMatrix(matrix.startX - step, matrix.startY, matrix.startX - 1, matrix.endY);
			else {
				change+= readMatrix(matrix.startX, matrix.startY, matrix.startX - step - 1, matrix.endY);	
				//cout << matrix.startX << " " << matrix.startX - step -1 << endl;
			}
		break;
	case RIGHT:	
		if (step > 0)
				change+= readMatrix(matrix.startX + 1, matrix.startY, matrix.endX + step, matrix.endY);
			else {
				change+= readMatrix(matrix.endX + step + 1, matrix.startY, matrix.endX, matrix.endY);
				//cout << matrix.endX + step + 1 << " " << 	matrix.endX << endl;
			}
		break;
	}
	cout << "Direzione: " << direction << " Step: "<< step << " Change: " << change << endl;
	return change;
}

int readMatrix(int startX, int startY, int endX, int endY) {
	int value = 0;
	
	for (int i = startY; i <= endY; i++) {
		for (int j = startX; j <= endX; j++) {
			value = value + array[i][j];
		}
	}
	
	return value;
}

void readArray() {
	start.value = INT_MIN;
	in >> rows >> columns;
	for (int i = 0; i < rows; i++) {
		for (int j = 0; j < columns; j++) {
			int n;
			in >> n;
			if (n > start.value) {
				start.value = n;
				start.x = j;
				start.y = i;
			}		
			array[i][j] = n;
		}
	}
	
}

void printMatrix() {
	cout << "startX:" << matrix.startX << " startY:" << matrix.startY << " endX:" << matrix.endX << " endY:" << matrix.endY << endl;
	for (int y = matrix.startY; y <= matrix.endY; y++) {
		for (int x = matrix.startX; x <= matrix.endX; x++) {
			cout << array[y][x] << " ";
		}
		cout << endl;
	}
	cout << "----------------------------------------" << endl;
}