Zadanie z Backtrackingu

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int SIZE = 8;

struct doubleCoords
{
    int x1;
    int y1;
    int x2;
    int y2;
};

bool operator <( const doubleCoords & a, const doubleCoords & b ) {
   
    if( a.x1 < b.x1 )
         return true;
    else if( a.x1 == b.x1 )
    {
        if( a.y1 < b.y1 )
             return true;
        else if( a.y1 == b.y1 )
        {
            if( a.x2 < b.x2 )
                 return true;
            else if( a.x2 == b.x2 )
            {
                if( a.y2 < b.y2 )
                     return true;
                else
                     return false;
               
            }
            else
                 return false;
           
        }
        else
             return false;
       
    }
    else
         return false;
   
}

struct coords
{
    int x; int y;
};

void print( vector < vector < char >> & board )
{
    for( int i = 0; i < SIZE; i++ )
    {
        for( int j = 0; j < SIZE; j++ )
             cout << board[ i ][ j ];
       
        cout << endl;
    }
    cout << endl;
}

void gravityDrop( vector < vector < char >> & board )
{
    for( int row = 0; row < SIZE; row++ )
    for( int col = 0; col < SIZE; col++ )
    if( board[ SIZE - row - 1 ][ col ] == '.' )
    {
        for( int up_row = SIZE - row - 1; up_row >= 0; up_row-- )
        {
            if( board[ up_row ][ col ] != '.' )
            {
                board[ SIZE - row - 1 ][ col ] = board[ up_row ][ col ];
                board[ up_row ][ col ] = '.';
                break;
            }
        }
    }
}

void SimplifyRows( vector < vector < char >> & board, doubleCoords & crds, vector < coords > & toRemove )
{
    //detect if swap was horizontal or vertical
    if( crds.y1 == crds.y2 ) //horizontal swap
    {
        int counter = 1;
        for( int i = 0; i < SIZE - 1; i++ )
        {
            if( board[ crds.y1 ][ i ] != '.' && board[ crds.y1 ][ i ] == board[ crds.y2 ][ i + 1 ] ) //if neighboring elements got the same value then increment counter
                 counter++;
            else
                 counter = 1;
           
            if( counter >= 3 ) //mark counted elements ro remove
            for( int j = i - counter + 2; j <= i + 1; j++ )
            toRemove.push_back( { crds.y1, j } );
        }
       
    }
    else //vertical swap
    {
        int counter = 1;
        for( int i = 0; i < SIZE - 1; i++ )
        {
            if( board[ crds.y1 ][ i ] != '.' && board[ crds.y1 ][ i ] == board[ crds.y1 ][ i + 1 ] ) //if neighboring elements got the same value then increment counter
                 counter++;
            else
                 counter = 1;
           
            if( counter >= 3 ) //mark counted elements ro remove
            for( int j = i - counter + 2; j <= i + 1; j++ )
            toRemove.push_back( { crds.y1, j } );
        }
       
        counter = 1; //the same algorithm have to be done because of vertical swap(we got upper and lower row)
        for( int i = 0; i < SIZE - 1; i++ )
        {
            if( board[ crds.y2 ][ i ] != '.' && board[ crds.y2 ][ i ] == board[ crds.y2 ][ i + 1 ] ) //if neighboring elements got the same value then increment counter
                 counter++;
            else
                 counter = 1;
           
            if( counter >= 3 ) //mark counted elements ro remove
            for( int j = i - counter + 2; j <= i + 1; j++ )
            toRemove.push_back( { crds.y2, j } );
           
        }
    }
}

void SimplifyCols( vector < vector < char >> & board, doubleCoords & crds, vector < coords > & toRemove )
{
    //detect if swap was horizontal or vertical
    if( crds.y1 == crds.y2 ) //horizontal swap
    {
        int counter = 1;
        for( int i = 0; i < SIZE - 1; i++ )
        {
            if( board[ i ][ crds.x1 ] != '.' && board[ i ][ crds.x1 ] == board[ i + 1 ][ crds.x1 ] ) //if neighboring elements got the same value then increment counter
                 counter++;
            else
                 counter = 1;
           
            if( counter >= 3 ) //mark counted elements ro remove
            for( int j = i - counter + 2; j <= i + 1; j++ )
            toRemove.push_back( { j, crds.x1 } );
        }
       
        counter = 1; //the same algorithm have to be done because of horizontal swap(we got left and right col)
        for( int i = 0; i < SIZE - 1; i++ )
        {
            if( board[ i ][ crds.x2 ] != '.' && board[ i ][ crds.x2 ] == board[ i + 1 ][ crds.x2 ] ) //if neighboring elements got the same value then increment counter
                 counter++;
            else
                 counter = 1;
           
            if( counter >= 3 ) //mark counted elements ro remove
            for( int j = i - counter + 2; j <= i + 1; j++ )
            toRemove.push_back( { j, crds.x2 } );
        }
    }
    else //vertical swap
    {
        int counter = 1;
        for( int i = 0; i < SIZE - 1; i++ )
        {
            if( board[ i ][ crds.x1 ] != '.' && board[ i ][ crds.x1 ] == board[ i + 1 ][ crds.x1 ] ) //if neighboring elements got the same value then increment counter
                 counter++;
            else
                 counter = 1;
           
            if( counter >= 3 ) //mark counted elements ro remove
            for( int j = i - counter + 2; j <= i + 1; j++ )
            toRemove.push_back( { j, crds.x1 } );
        }
    }
}

pair < vector < vector < char >>, int > makeMove( vector < vector < char >> board, doubleCoords & crds, int score )
{
    //swap works
    swap( board[ crds.y1 ][ crds.x1 ], board[ crds.y2 ][ crds.x2 ] );
    vector < coords > toRemove;
    int removedPositions = 0;
   
    do
    {
        toRemove.clear(); //clear vector before reuse
        //Gravity drop /works
        gravityDrop( board );
        //Simplify cols
        SimplifyCols( board, crds, toRemove );
        //Simplify rows
        SimplifyRows( board, crds, toRemove );
       
        if( toRemove.size() > 0 ) //if theres any positions to clear
        {
            removedPositions += toRemove.size();
            for( coords remove: toRemove )
            {
                board[ remove.x ][ remove.y ] = '.';
            }
        }
       
    } while( toRemove.size() > 0 ); //repeat till it is greater than 0
   
    return make_pair( board, score - removedPositions );
}

/*pair<vector<vector<char>>,int> makeMove(vector<vector<char>> board, doubleCoords & crds, int score)
{
    //swap works
    swap(board[crds.y1][crds.x1], board[crds.y2][crds.x2]);
    vector<coords> toRemove;
   
    SimplifyRows(board, crds, toRemove);
    SimplifyCols(board, crds, toRemove);
   
    for(coords remove : toRemove)
    {
        board[remove.x][remove.y] = '.';
    }
    gravityDrop(board);
   
    return make_pair(board, score-toRemove.size());
}*/

vector < doubleCoords > solve( vector < vector < char >> & board, int score, vector < doubleCoords > moves = vector < doubleCoords >(), int level = 0 )
{
    if( score == 0 )
         return moves; //if we cleard the board
    else if( level == 8 )
         return vector < doubleCoords >(); //if we've reached the limit
    else //if we still got moves
    {
        vector < doubleCoords > bestSequence( 9 );
        doubleCoords tempCoords;
        for( int i = 0; i < SIZE; i++ )
        for( int j = 0; j < SIZE - 1; j++ )
        {
            pair < vector < vector < char >>, int > newBoardPair; //board and score obtained because of move
            vector < doubleCoords > newMoves;
           
            //conditional required to swap elements, theres no use of swap empty positions
            if( board[ i ][ j ] != '.' || board[ i ][ j + 1 ] != '.' )
            {
                //cout << "H: " << board[i][j] << " " << board[i][j+1] << endl;
                tempCoords.x1 = j; tempCoords.y1 = i; tempCoords.x2 = j + 1; tempCoords.y2 = i;
                newBoardPair = makeMove( board, tempCoords, score ); //horizontal move
                if( newBoardPair.second < score )
                {
                    moves.push_back( tempCoords );
                    newMoves = solve( board, newBoardPair.second, moves, level + 1 );
                    moves.pop_back();
                   
                    if( newMoves.size() < bestSequence.size() )
                         bestSequence = newMoves;
                    else if( newMoves.size() == bestSequence.size() && lexicographical_compare( newMoves.begin(), newMoves.end(), bestSequence.begin(), bestSequence.end() ) )
                         bestSequence = newMoves;
                   
                }
            }
           
            //the same conditional as above
            if( board[ j ][ i ] != '.' && board[ j + 1 ][ i ] != '.' )
            {
                //cout << "V: " << board[j][i] << " " << board[j+1][i] << endl;
                tempCoords.x1 = i; tempCoords.y1 = j; tempCoords.x2 = i; tempCoords.y2 = j + 1;
                newBoardPair = makeMove( board, tempCoords, score ); //vertical move
                if( newBoardPair.second < score )
                {
                    moves.push_back( tempCoords );
                    newMoves = solve( board, newBoardPair.second, moves, level + 1 );
                    moves.pop_back();
                   
                    if( newMoves.size() < bestSequence.size() )
                         bestSequence = newMoves;
                    else if( newMoves.size() == bestSequence.size() && lexicographical_compare( newMoves.begin(), newMoves.end(), bestSequence.begin(), bestSequence.end() ) )
                         bestSequence = newMoves;
                   
                }
            }
           
        }
       
        return bestSequence;
    }
}

int main( int argc, const char * argv[] ) {
   
    vector < vector < char >> data;
    int firstScore = 0;
    for( int y = 0; y < SIZE; y++ )
    {
        vector < char > temp( SIZE );
        for( int x = 0; x < SIZE; x++ )
        {
            cin >> temp[ x ];
            if( temp[ x ] != '.' )
                 firstScore++;
           
        }
        data.push_back( temp );
    } //read
    vector < doubleCoords > result = solve( data, firstScore );
    cout << result.size() << endl;
    for( doubleCoords & crds: result ) //display result
         cout << crds.y1 + 1 << " " << crds.x1 + 1 << " " << crds.y2 + 1 << " " << crds.x2 + 1 << endl;
   
    return 0;
}