10895 – Matrix Transpose UVA Solution

This a is tedious but easy problem from uva judge https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1836

• I read the number of rows and columns from the matrix(rows, cols).
• I initialize two graphs. vec with the numbers of rows equal to “rows” and adj with the number if rows equal to “cols”.
• I save each matrix row input into 2 vectors.
• I build the graph with this structure vector<vector<pair<int,int> > >. pair<int,int> is column number and value of the cell.
• I transpose traversing the vec graph and I save the result in adj graph.
• I print the answer.
• Accepted!

Hints

• It’s necessary to save the column number and cell value.

Code

/*
*Author: Fabian Calsina
*Date: 25/11/2016
*/
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;

vector<vector <ii> > vec;
vector<vector <ii> > adj;

void setRow(vi vIndex, vi vValue, int rowIndex){

    //pair<int,int> = (column, value)
    pair<int,int> tmp;

    for(int x=0; x<vIndex.size(); x++){
        tmp.first  = vIndex[x];
        tmp.second = vValue[x];
        vec[rowIndex].push_back(tmp);
    }
}

void printAnswer(int rows, int cols){

    vector<ii> answerRow;
    printf("%d %d\n", cols, rows);

    for(int a=0; a<adj.size(); a++){
        answerRow = adj[a];

        if(!answerRow.size()){
            printf("0\n\n");
        }
        else{
            printf("%d", answerRow.size());
            //pair<int,int> = (column, value)
            for(int c=0; c<answerRow.size(); c++){
                printf(" %d", answerRow[c].first + 1);
            }
            printf("\n");
            //pair<int,int> = (column, value)
            for(int d=0; d<answerRow.size(); d++){
                if(d < answerRow.size()-1)
                    printf("%d ", answerRow[d].second);
                else
                    printf("%d\n", answerRow[d].second);
            }
        }
    }
}

int main(){
    int rows, cols, noEmpty, val;
    vi vIndex, vValue;
    ii tmp, tmpA;
    string trash;

    while(scanf("%d %d", &rows, &cols) != EOF){
        vec.assign(rows, vector<ii>());
        adj.assign(cols, vector<ii>());

        for(int a=0; a<rows; a++){
            scanf("%d", &noEmpty);
            if(!noEmpty){
                getline(cin, trash);
                continue;
            }
            //Read indexes
            for(int b=0; b<noEmpty; b++){
                cin>>val;
                vIndex.push_back(val-1);
            }
            //Red values
            for(int b=0; b<noEmpty; b++){
                cin>>val;
                vValue.push_back(val);
            }
            //Set graph
            //a Is the row of the graph
            setRow(vIndex, vValue, a);
            vIndex.clear();
            vValue.clear();
        }

        for(int x=0; x<vec.size(); x++){
            for(int y=0; y<vec[x].size(); y++){
                tmp = vec[x][y];
                tmpA.first = x;
                tmpA.second = tmp.second;
                adj[tmp.first].push_back(tmpA);
            }
        }
        printAnswer(rows,cols);
    }
return 0;
}