proyecto.cpp

An example of a divide and conquer algorithm

#include <iostream.h> 
#include <Math.h> 
#include <conio.h>


void triomino(int firstRow, int lastRow, int firstColumn, int lastColumn, int esp_r, int esp_c); 

static int cont; 
static int mat[132][132]; 

void triomino(int firstRow, int lastRow, int firstColumn, int lastColumn, int esp_r, int esp_c) 
{ 
    if((lastRow - firstRow) == 2) // Compruebo si cumple con el caso base que es cuando el tama駉 es 2.
    { 
        for(int i = firstRow; i <lastRow;i++) 
        { 
            for(int j = firstColumn ; j < lastColumn; j++) 
            { 
                if(i != esp_r || j != esp_c)
                { 
                    mat[i][j] = cont; 
                } 
            } 
        } 
        cont++;
    }else 
    { 
        int row_m = (lastRow + firstRow) /2; 
        int col_m = (firstColumn + lastColumn) / 2;
        
        if(esp_r <= row_m && esp_c < col_m) //Revisa si el espacio esta en el primer cuadrante.
        { 
            mat[row_m-1][col_m] = cont; 
            mat[row_m][col_m-1] = cont; 
            mat[row_m][col_m] = cont; 
            cont++; 
            triomino(firstRow,row_m,firstColumn,col_m,esp_r,esp_c);
            triomino(firstRow,row_m, col_m,lastColumn,row_m-1,col_m); 
            triomino(row_m,lastRow,col_m,lastColumn, row_m,col_m); 
            triomino(row_m,lastRow,firstColumn,col_m,row_m,col_m-1); 
        }else if (esp_r < row_m && esp_c >= col_m) //Revisa si el espacio esta en el 2 Cuadrante
        { 
            mat[row_m-1][col_m-1] = cont; 
            mat[row_m][col_m] = cont; 
            mat[row_m][col_m-1] = cont; 
            cont++; 
            triomino(firstRow,row_m,firstColumn,col_m,row_m-1,col_m-1); 
            triomino(firstRow,row_m,col_m,lastColumn,esp_r,esp_c); 
            triomino(row_m,lastRow,col_m,lastColumn,row_m,col_m); 
            triomino(row_m,lastRow,firstColumn,col_m,row_m,col_m-1); 
        }else if(esp_r >= row_m && esp_c >= col_m) //Revisa si el espacio esta en el 3 cuadrante
        { 
            mat[row_m-1][col_m-1] = cont; 
            mat[row_m-1][col_m] = cont; 
            mat[row_m][col_m-1] = cont; 
            cont++; 
            triomino(firstRow,row_m,firstColumn,col_m,row_m-1,col_m-1); 
            triomino(firstRow,row_m,col_m,lastColumn,row_m-1,col_m); 
            triomino(row_m,lastRow,col_m,lastColumn,esp_r,esp_c); 
            triomino(row_m,lastRow,firstColumn,col_m,row_m,col_m-1);  
        }else if(esp_r >= row_m && esp_c <= col_m) //Revisa si el espacio esta en el 4 cuadrante
        { 
            mat[row_m-1][col_m-1] = cont; 
            mat[row_m-1][col_m] = cont; 
            mat[row_m][col_m] = cont; 
            cont++;
            triomino(firstRow,row_m,firstColumn,col_m,row_m-1,col_m-1); 
            triomino(firstRow,row_m,col_m,lastColumn,row_m-1,col_m); 
            triomino(row_m,lastRow,col_m,lastColumn,row_m,col_m); 
            triomino(row_m,lastRow,firstColumn,col_m,esp_r,esp_c);  
        } 
    } 

} 


void main() 
{ 
    int row, col, esp_r, esp_c; 
    cout<< "de que tama駉 va a ser la matriz (2^i)?:";  //El usuario define el tama駉 de la matriz.
    cin>> row; 
    cout<< "Dame el renglon donde estar el espacio en blanco:";
    cin>> esp_r;
    cout<< "Dame la columna donde va a estar el espacio en blanco:";
    cin>> esp_c;
    row = pow(2.0, row); 
    col = row ; 
    cont = 0;  
    mat[esp_r][esp_c] = -1; 
    triomino(0,row,0,col,esp_r,esp_c);
    for (int i = 0; i < row; i++) // Despliego la matriz en pantalla.
    { 
        for (int j = 0; j < col ; j++) 
        { 
            cout << mat[i][j] << "  "; 
        } 
        cout << endl; 
    } 
    getche();
}  

// El orden de mi algoritmo es exponencial.