Laser brute force

laser.cpp

#include <stdio.h>
#include <assert.h>
#include <vector>
#include <time.h>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

#define MAXM 30

clock_t tStart;

// prints number in matrix, -1 for "no node"
void print(FILE *fw, int num) {
    if (num == -1) fprintf(fw, " . ");
    else fprintf(fw, "%2d ", num);
}

double getExecutionTime() {
    return (double) (clock() - tStart) / CLOCKS_PER_SEC;
}

int A[MAXM];
int B[MAXM];
int collegamentiMax = -1;

int main() {
    tStart = clock();
    FILE *fr, *fw;
    int H, W, N, M, i, j;

    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    assert(4 == fscanf(fr, "%d %d %d %d", &H, &W, &N, &M));

    int numList[N];
    for (int i = 0; i < N; i++) {
        numList[i] = i;
    }

    for (i = 0; i < M; i++)
        assert(2 == fscanf(fr, "%d %d", &A[i], &B[i]));


    int matrix[H][W];

    int x[] = {1, -1};
    int y[] = {1, -1};

    int last[H][W];

    vector<pair<int, int> > collegamentiRichiesti;

    for (int i = 0; i < N; i++) {
        if (A[i] > B[i]) {
            collegamentiRichiesti.push_back(pair<int, int>(B[i], A[i]));
        } else {
            collegamentiRichiesti.push_back(pair<int, int>(A[i], B[i]));
        }
    }

    vector<pair<int, int> > collegamentiOrizzontali;
    vector<pair<int, int> > collegamentiVerticali;

    vector<int> in;

    while (getExecutionTime() < 3.9) {
        collegamentiOrizzontali.clear();
        collegamentiVerticali.clear();

        for (i = 0; i < H; i++) {
            for (j = 0; j < W; j++) {
                matrix[i][j] = -1;
            }
        }
        for (int i = 0; i < N; i++) {
            while (true) {
                int x = rand() % H;
                int y = rand() % W;



                if (matrix[x][y] == -1) {
                    matrix[x][y] = i;
                    break;
                }
            }
        }

        // CALCOLO COLLEGAMENTI ORIZZONTALI
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W - 1; j++) {
                if (matrix[i][j] == -1)
                    continue;
                int indexOfNext = j + 1;
                while (matrix[i][indexOfNext] == -1 && indexOfNext < W) {
                    indexOfNext++;
                }
                if (indexOfNext < W) {
                    if (matrix[i][indexOfNext] > matrix[i][j]) {
                        collegamentiOrizzontali.push_back(pair<int, int>(matrix[i][j], matrix[i][indexOfNext]));
                    } else {
                        collegamentiOrizzontali.push_back(pair<int, int>(matrix[i][indexOfNext], matrix[i][j]));
                    }
                } else {
                    continue;
                }
            }
        }
        // END COLLEGAMENTI ORIZZONTALI

        // CALCOLO COLLEGAMENTI VERTICALI
        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                if (matrix[i][j] == -1)
                    continue;
                int indexOfNext = i + 1;
                while (matrix[indexOfNext][j] == -1 && indexOfNext < H) {
                    indexOfNext++;
                }
                if (indexOfNext < H) {
                    if (matrix[indexOfNext][j] > matrix[i][j]) {
                        collegamentiVerticali.push_back(pair<int, int>(matrix[i][j], matrix[indexOfNext][j]));
                    } else {
                        collegamentiVerticali.push_back(pair<int, int>(matrix[indexOfNext][j], matrix[i][j]));
                    }
                } else {
                    continue;
                }
            }
        }
        // END COLLEGAMENTI VERTICALI

        // CALCOLO BONTA'
        int collegamenti = 0;
        for (int i = 0; i < collegamentiRichiesti.size(); i++) {
            int first = collegamentiRichiesti[i].first;
            int second = collegamentiRichiesti[i].second;
            pair<int, int> query(
                    first < second ? first : second,
                    first < second ? second : first
            );

            for (int x = 0; x < collegamentiOrizzontali.size(); x++) {
                if (query.first == collegamentiOrizzontali[x].first &&
                    query.second == collegamentiOrizzontali[x].second) {
                    collegamenti++;
                    continue;
                }
            }
            for (int y = 0; y < collegamentiVerticali.size(); y++) {
                if (query.first == collegamentiVerticali[y].first &&
                    query.second == collegamentiVerticali[y].second) {
                    collegamenti++;
                    continue;
                }
            }
        }

        bool isCorrupted = false;

        for (int i = 0; i < H; i++) {
            for (int j = 0; j < W; j++) {
                for(int g=0;g<in.size();g++){
                    if(in[g]==matrix[i][j]){
                        isCorrupted = true;
                        goto outtaLoop;
                    }else{
                        in.push_back(matrix[i][j]);
                    }
                }
            }
        }

        outtaLoop:

        if (collegamentiMax < collegamenti && !isCorrupted) {
            collegamentiMax = collegamenti;
            for (int i = 0; i < H; i++) {
                for (int j = 0; j < W; j++) {
                    last[i][j] = matrix[i][j];
                }
            }
        }
        // END CALCOLO BONTA'

    }

    for (i = 0; i < H; i++) {
        for (j = 0; j < W; j++)
            print(fw, last[i][j]);
        fprintf(fw, "\n");
    }
    fclose(fr);
    fclose(fw);
    return 0;
}