103 DP 2dArray fgets sscanf

/*
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
*/
#include <stdio.h>
#include <stdlib.h>
/*#include <string.h>*/
typedef enum __bool{  
    false=0,
    true=1,
}bool;

void print2d(int** a,int m,int n);
void al2d(int*** a,int m,int n);
void f2d(void*** a,int m);
void sort(int **a,int n){
    /*printf("sort %d ",n);*/
    int i,j,max;
    for(i=0;i<n-1;i++){
        max=i;
        /*printf("i = %d %d %d,",i,(*a)[i],&(*a)[i]);*/
        for(j=i+1;j<n;j++){
            /*printf("j = %d %d %d,",j,(*a)[j],&(*a)[j]);*/
            if((*a)[j]>(*a)[max]){
                max=j;              
            }
        }
        /*printf("max = %d %d,",max,(*a)[max]);*/
        if(max!=i){
            int t=(*a)[i];
            (*a)[i] = (*a)[max];
            (*a)[max] = t;
        }
        /*printf("\n");*/
    }
}

void atoi_n(int** input,char *c,int n){
    int i=0;
    /*c[strlen(c)-1]='1';*/
    int tn=n;
    while(n>0){
        int cc = atoi(c);
        /*printf("c %s\n",c);
        printf("cc %d\n",cc);*/
        (*input)[i] = cc;
        cc++;
        /*printf("%s",c);*/
        while((*c)!='\n' && (*c)!=' ' && (*c)!='\0'){
             /*printf("*c = %c %d,\n",*c,&c);*/
             c++;
             /*system("PAUSE");*/
        }
        c++;
        i++;
        n--;
    }
    sort(&(*input),tn);  
}

int AnetsB(int* A,int *B,int n){
    int i;
    for(i=0;i<n;i++){
        if((A)[i]<=(B)[i]){
            return 0;
        }
    }
    return 1;
}

void _AnetsB(int*** net,int **input,int m,int n){
    int i,j;
    for(i=0;i<m;i++){      
        for(j=0;j<m;j++){
            if(i==j){
                (*net)[i][j]=0;
                continue;
            }
            (*net)[i][j] = AnetsB(input[i],input[j],n);
        }
    }
}
void** creat2D(int m,int n){
    void** a;
    a = malloc(m*sizeof(int*));  
    int i,j;
    for(i=0;i<m;i++){
        a[i]= malloc(n*sizeof(int));      
    }
    return a;
}
int getMax(int *a,int n,int *c){
    int max=0;
    int i;
    for(i=0;i<n;i++){
        if(a[max]<a[i])
        {
            max=i;
        }
    }
    *c = max;
    return a[max];
}
void addDP(int ***a,int n){
    bool debug=true;
    int i=0,j,k;
    for(i=2;i<n;i++){
        for(j=0;j<n;j++){
            int count=0;          
            for(k=0;k<n;k++){
                if((*a)[j][k]>0){
                    count++;
                }
            }
            if(count==i){
                for(k=0;k<n;k++){
                    if((*a)[j][k]>0){
                        int t;
                        (*a)[j][k] += getMax((*a)[k],n,&t);
                    }
                }
            }
        }
    }

}

void printAns(int **a,int n){
    bool debug=false;
    int i,j;
    int max=0,maxLine;
    /*for(i=n-1;i>=0;i--){*/
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(a[i][j]>max){
                max=a[i][j];
                maxLine=i;
            }
        }
    }
    printf("%d\n",max+1);
    /*printf("%d ",maxLine+1);*/
    int *ansS = malloc(max* sizeof(int));
    int top=0;
    ansS[top++] = maxLine+1;
    for(i=max;i>0;i--){  
        /*for(j=n-1;j>=0;j--){*/
        int column;
        if(debug)printf("ansS[top-1] %d ",ansS[top-1]);
        getMax(a[ansS[top-1]-1],n,&column);
        if(debug)printf("column %d \n",column+1);
        /*ansS[top++] = getMax(a[j],n);/*printf("%d ",j+1);*/
        ansS[top++] = column+1;
      
    }
    /*print1
    printf("%d",ansS[top-1]);
    for(j=top-2;j>=0;j--){
        printf(" %d",ansS[j]);
    }*/

    /*print2*/      
    for(j=top-1;j>0;j--){
        printf("%d ",ansS[j]);
    }
    printf("%d",ansS[0]);
  
    printf("\n");
    free(ansS);
}
int main()
{
    /*int *input1d;
    al1d(&input1d,5);
    print1d(input1d,5);*/
    bool debug=false;
    int **input;
    int **nets;
    int m,n;
    char line[512];
    /*while(scanf("%d %d",&m,&n)!=EOF){*/
    while(fgets(line,512,stdin)!= NULL){
        /*printf("\n%s",line);*/
        sscanf(line,"%d %d",&m,&n);
        /*printf("%d %d\n",m,n);*/
        if(m==0){
            printf("0\n\n");
            continue;
        }
        /*al2d(&input,m,n);*/
        input = (int**)creat2D(m,n);
/*        nets = (bool**)malloc(m*sizeof(bool*)+m*n*sizeof(bool));*/
        nets = (int**)creat2D(m,m);

        int co_line=0;
        while(co_line<m){
            fgets(line,512,stdin);
            /*putc('\0',line);*/
            /*printf("\n%s",line);*/
            atoi_n(&input[co_line],line,n);
            /*print2d(input,m,n);        */
            co_line++;          
        }
        int i,j;      

        if(debug)print2d(input,m,n);
        _AnetsB(&nets,input,m,n);
        if(debug)print2d(nets,m,m);
        addDP(&nets,m);
        if(debug)print2d(nets,m,m);
        if(m==1){
            printf("0\n\n");
        }
        else{
            printAns(nets,m);
        }
        f2d(&input,m);
        f2d(&nets,m);      
    }  
    if(debug)system("PAUSE");
    return 0;
}

void print2d(int** a,int m,int n){
    int i,j;
    printf("\n");
    for(i=0;i<m;i++){
        for(j=0;j<n;j++){
            printf("%d ",a[i][j]);
        }
        printf("\n");
    }
  
}
 
void print1d(int* pa,int m){
    int i;
    for(i=0;i<m;i++){
        printf("%d",pa[i]);
    }
}          
void al1d(int **pa,int m){
  
    *pa = malloc(sizeof(int)*m);
    int i;
    for(i=0;i<m;i++){
        (*pa)[i]=1;
        /*printf("%d",(pa[i]));*/
    }
    print1d(*pa,m);
}
void al2d(int*** a,int m,int n){
    *a = malloc(m*sizeof(int*));
  
    int i,j;
    for(i=0;i<m;i++){
        (*a)[i]= malloc(n*sizeof(int));
        for(j=0;j<n;j++){
            (*a)[i][j]= 0;
            /*printf("%d ",(*a)[i][j]);*/
        }
        /*printf("\n");*/
    }
    /*print2d(*a,m,n);*/
}
void f2d(void*** a,int m){
  
  
    int i,j;
    for(i=0;i<m;i++){
        free((*a)[i]);
    }
    free(*a);
}