Riempimento matrice

[franbisc]

Devo scrivere in C++ una funzione che riempie una matrice non necessariamente quadrata di numeri crescenti a spirale,dai margini esterni verso l'interno.
Questo è il mio codice,che compila... ma da altri errori a run time.

void spirale(vector< vector<int> > &v)
{
    int rows = v.size();
    int cols = v[0].size();

    // prima cella:in basso a sinistra
    int  x=0 , y= rows-1;
    //primo spostamento:verso l'alto
    int dy = -1, dx = 0;

    for(int i=1; i<=rows*cols; i++)  {

        v[y][x]= i;
        y += dy; x += dx;

        // se tocca il bordo superiore o la prossima cella in alto è già riempita ...
        if (y <=0 || v[y-1][x]!=0 ) {
           dy = 0; dx=+1;
           y += dy; x += dx;
        }
        // se tocca il bordo destro  o la prossima cella a destra è già riempita...
        if ( x >= cols || v[y][x+1]!=0 )  {
            dy = +1; dx=0;
            y += dy; x += dx;
        }
        // se tocca il bordo inferiore  o la prossima cella in basso è già riempita...
        if ( y >= rows || v[y+1][x]!=0 )  {
            dy = 0; dx=-1;
            y += dy; x += dx;
        }
        // se tocca il bordo sinistro  o la prossima cella a sinistra è già riempita...
        if ( x <=0 || v[y][x-1]!=0 ) {
           dy = -1; dx=0;
           y += dy; x += dx;
        }

    }
}

Riuscite ad aiutarmi?

[vict85]

Prima di incominciare con il codice un piccolo appunto:

La prima cosa che devi sapere quando hai a che fare con le matrici è che NESSUN programmatore serio userebbe un vector di vector per una matrice. In gran parte perché l'implementazione sarebbe assolutamente lenta, poco gestibile e inutilmente complessa.

Il mio consiglio è definire una classe matrice come:

class int_matrix
{
public:
    matrix() : data_m(), row_m(0), cols_m(0) { }
    matrix(const unsigned row, const unsigned cols) : data_m(row*cols, 0) , row_m(row), cols_m(cols_m) { }
    matrix(const matrix &M) : data_m(M.data_m), row_m(M.row_m), cols_m(M.cols_m) { }
    
    matrix & operator= (const matrix &M)
    {
        data_m = M.data_m;
        row_m = M.row_m;
        cols_m = M.cols_m;
        return *this;
    } 

    int & operator() (unsigned const i, unsigned const j)
    {
        return data_m[i*cols_m + j];
    }

    unsigned size1()
    {
        return row_m;
    }
    unsigned size2()
    {
        return cols_m;
    }
private:
    vector<int> data_m;
    unsigned row_m;
    unsigned cols_m;
}

Questa classe ha la seguente sintassi:

M.size1() è il numero di righe
M.size2() è il numero di colonne
M(i,j) è l'elemento \(\displaystyle M_{i\ j} \)

più semplice di così L'unica cosa che è difficile, quasi impossibile fare con questa classe è cambiare la dimensione della matrice. Per questa ragione bisognerebbe impedire di creare la matrice come matrix M; senza esplicitarne la dimensione. Si può creare una classe più completa ovviamente, che permetta questa operazione e che impedisca di creare una matrice vuota (questo è facile da fare basta nel senso che basta mettere il costruttore di default come private).
Una classe di questo tipo andrebbe sempre passato per reference.

###############################

Che main hai? Io ho usato questo:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    unsigned Row = 10;
    unsigned Col = 10;
    vector< vector<int> > M(Row, vector<int>(Col, 0));
    spirale(M);
    cout<<"["<<M.size()<<","<<M[0].size()<<"]"<<endl;
    for(int i= 0; i!= M.size(); ++i)
    {
        cout<<"[";
        for(int j=0; j!=M[0].size()-1; ++j)
        cout<<M[i][j]<<", ";
        cout<<M[i][M[0].size()-1]<<"]"<<endl;
    }
    return 0;
}

L'ho provato e dovrebbe funzionale.

La tua funzione ha invece un errore piuttosto semplice: hai tentato di accedere ad un (i,j) fuori dalla matrice. Devi solo capire dove. Sinceramente comunque non penso che il tuo sia l'approccio corretto ma non ho capito completamente cosa dovrebbe fare la funzione. Potresti farci un esempio con una matrice quadrata e con una rettangolare?

[franbisc]

"vict85":La prima cosa che devi sapere quando hai a che fare con le matrici è che NESSUN programmatore serio userebbe un vector di vector per una matrice

Scelta del professore...

"vict85":Che main hai?

Nel main chiedo all'utente i due int rows e cols,che poi uso per inizializzare la matrice con:

vector< vector<int> > matrix(rows,vector<int>(cols,0))

Dopodichè passo la matrice alla funzione,con

spirale(matrix)

"vict85":Sinceramente comunque non penso che il tuo sia l'approccio corretto ma non ho capito completamente cosa dovrebbe fare la funzione. Potresti farci un esempio con una matrice quadrata e con una rettangolare?

Nel caso di una matrice quadrata, ad esempio:
$ ( ( 3 , 4 , 5 ),( 2 , 9 , 6 ),( 1 , 8 , 7 ) ) $
Mentre,se rettangolare:
$ ( ( 3 , 4 , 5 , 6 ),( 2 , 11 , 12 , 7 ),( 1 , 10 , 9 , 8 ) ) $

*****************************************************
PS:non riesco ad individuare l'errore...

[franbisc]

Anzi,credo di aver individuato l'errore,che sta nei vari:

v[y][x+1]!=0

dentro i 4 if,ma anche correggendo con

v[y][x]!=0

comunque non va

[claudio862]

@Mifert4
Stampa i valori di x e y ad ogni iterazione e vedrai che assumono valori negativi.

...

    for(int i = 1; i <= rows*cols; i++)  {
        std::cout << "x: " << x << ", y: " << y << std::endl;
        v[y][x] = i;
        y += dy; x += dx;

        ...

@vict85
Il costruttore di copia e l'operatore di assegnamento che hai definito sono uguali a quelli impliciti, quindi è meglio lasciar fare al compilatore. Gli altri due costruttori invece si possono combinare in uno solo, con argomenti di default. Dovresti anche replicare l'operatore () per oggetti costanti.

class int_matrix
{
public:
    int_matrix(int rows = 0, int columns = 0)
     : data_(rows*columns, 0),
       rows_(rows),
       columns_(columns)
    {
    }

    int & operator() (int i, int j)
    {
        return data_[i*columns_ + j];
    }

    int operator() (int i, int j) const
    {
        return data_[i*columns_ + j];
    }

    int rows()
    {
        return rows_;
    }

    int columns()
    {
        return columns_;
    }

private:
    std::vector<int> data_;
    int rows_;
    int columns_;
};

[franbisc]

"claudio86":@Mifert4
Stampa i valori di x e y ad ogni iterazione e vedrai che assumono valori negativi

Dopo avere apportato questa modifica:

        if (y <0 || v[y][x]!=0 ) {
           dy = 0; dx=+1;
           y += dy; x += dx;
        }
        if ( x >= cols || v[y][x]!=0 )  {
            dy = +1; dx=0;
            y += dy; x += dx;
        }
        if ( y >= rows || v[y][x]!=0 )  {
            dy = 0; dx=-1;
            y += dy; x += dx;
        }
        if ( x <0 || v[y][x]!=0 ) {
           dy = -1; dx=0;
           y += dy; x += dx;
        }

nel caso,ad esempio,di una matrice 5x5 riesco a visualizzare i primi 5 valori che sono:
x: 0, y: 4
x: 0, y: 3
x: 0, y: 2
x: 0, y: 1
x: 0, y: 0

cioè esattamente come dovrebbe essere,il problema viene proprio ora,cioè quando dovrebbe "svoltare a destra"

[claudio862]

Allora mi accodo alla richiesta di vict85, mostra il main(). Usando quello di vict85 e la tua funzione spirale() a me viene questo:

x: 0, y: 9
x: -1, y: 7
x: 0, y: 5
x: -1, y: 3
x: 0, y: 1
x: 1, y: 0
x: 3, y: 0
x: 5, y: 0
x: 7, y: 0
x: 9, y: 1
x: 9, y: 3
x: 8, y: 4
x: 9, y: 6
x: 9, y: 8

[franbisc]

*/***********MAIN***********/
#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

 int main()  {
    int rows,cols;
    cout<<"Rows= ";
    cin>>rows;
    cout<<"Columns= ";
    cin>>cols;

    vector< vector<int> > matrix(rows,vector<int>(cols,0));
    spirale(matrix);

    for(int i=0; i<rows; i++) {
        for(int j=0; j<cols; j++) {
            cout <<setw(4)<< matrix[i][j];
        }
        cout<<endl;
    }

    return 0;
}

[claudio862]

Credo che ad ogni iterazione tu debba prima capire in che direzione ti stai muovendo, e solo dopo controllare se hai sbattuto contro un bordo. Soprattutto per la seconda condizione, v[x][y] != 0, che viene controllata in tutti gli if (e quindi entra sempre nel primo).
Poi, una volta che sai di aver sbattuto contro qualcosa (es. y < 0) devi prima tornare nel punto precedente, cambiare direzione, ed avanzare di nuovo.

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;


void print(vector< vector<int> > &matrix)
{
    int rows = matrix.size();
    int cols = matrix[0].size();
    for(int i=0; i<rows; i++) {
        for(int j=0; j<cols; j++) {
            cout <<setw(4)<< matrix[i][j];
        }
        cout<<endl;
    }
    cout << endl;
}

void spirale(vector< vector<int> > &v)
{
    int rows = v.size();
    int cols = v[0].size();

    // prima cella:in basso a sinistra
    int  x=0 , y= cols-1;
    //primo spostamento:verso l'alto
    int dy = -1, dx = 0;

    for(int i=1; i<=rows*cols; i++)  {

        v[x][y]= i;

        y += dy; x += dx;

        if (dx == 0 && dy == -1) {
            // Sto andando in su.

            if (y < 0 || v[x][y] != 0) {
                // se tocca il bordo superiore o la prossima cella
                // in alto è già riempita.

                // Torna al punto precedente.
                y -= dy; x -= dx;

                // Cambia direzione
                dy = 0;
                dx = +1;

                // Avanza di nuovo.
                y += dy; x += dx;
            }
        } else if (dx == 0 && dy == 1) {
            // Sto andando in giu.

            if (y >= cols || v[x][y] != 0) {
                // se tocca il bordo inferiore o la prossima cella
                // in basso è già riempita.

                // Torna al punto precedente.
                y -= dy; x -= dx;

                // Cambia direzione
                dy = 0;
                dx = -1;

                // Avanza di nuovo.
                y += dy; x += dx;
            }
        } else if (dx == 1 && dy == 0) {
            // Sto andando a destra.

            if (x >= rows || v[x][y] != 0) {
                // se tocca il bordo destro o la prossima cella
                // a destra è già riempita.

                // Torna al punto precedente.
                y -= dy; x -= dx;

                // Cambia direzione
                dy = +1;
                dx = 0;

                // Avanza di nuovo.
                y += dy; x += dx;
            }
        } else if (dx == -1 && dy == 0) {
            // Sto andando a sinistra.

            if (x < 0 || v[x][y] != 0) {
                // se tocca il bordo sinistro o la prossima cella
                // in a sinistra è già riempita.

                // Torna al punto precedente.
                y -= dy; x -= dx;

                // Cambia direzione
                dy = -1;
                dx = 0;

                // Avanza di nuovo.
                y += dy; x += dx;
            }
        }
    }
}

int main()  {
    int rows,cols;
    cout<<"Rows= ";
    cin>>rows;
    cout<<"Columns= ";
    cin>>cols;

    vector< vector<int> > matrix(rows,vector<int>(cols,0));
    spirale(matrix);//per passare il vector non serve &

    print(matrix);

    return 0;
}

Nota che ho invertito x e y, nel caso scambiale di nuovo. Magari qualcun altro trova un modo più sintetico.