Skip to content

Instantly share code, notes, and snippets.

@mion00

mion00/sottomat.cpp

Created October 7, 2014 17:11
Show Gist options
  • Save mion00/07103b9b87af9f59efe8 to your computer and use it in GitHub Desktop.
Save mion00/07103b9b87af9f59efe8 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment