下三角矩阵

描述

给定一个由0和1组成的矩阵。只允许交换相邻的两行,要把矩阵转化成下三角矩阵（主对角线上方的元素都是0），最少需要交换几次？输入的矩阵保证总能转化成下三角矩阵。

输入

多组测试数据。
每组测试数据第一行为一个整数n（1 <= n < 1000），表示矩阵的大小为n*n；
接下来n行，每行有n个数表示这个矩阵。

输出

输出最小需要交换的次数，单独占一行。

样例输入

3

0 0 1

1 0 0

0 1 0

样例输出

2

思路:先记录第i行最后一个1的列(位置)num[i],然后从第一行起，for i 1->end,for j i-->end,有num[j]<=i,从第j行起依次与前面的行交换顺序,到第i行为止

同时记录交换次数j-i,和即为最小的次数

#include <stdio.h>

#include <string.h>

int a[][];

int num[];

int main()

{

    int n,i,j,pos,ans;

    while(~scanf("%d",&n))

    {

        for(i=;i<n;i++)

            for(j=;j<n;j++)

            {

                scanf("%d",&a[i][j]);

            }

        memset(num,,sizeof(n));//默认的列为0

        //确定最后一个1的列

        for(i=;i<n;i++)

            for(j=n-;j>=;j--)

            {

                if(a[i][j])

                {

                    num[i] = j;

                    break;//一定要break

                }

            }

        ans = ;//计算每组数据交换次数之前都初始化为0

        //从第一行开始移动

        for(i=;i<n;i++)

        {

            for(j=i;j<n;j++)

            {

                if(num[j] <= i)//要发生交换

                {

                    pos = j;

                    break;

                }

            }

            for(j=pos;j>i;j--)

            {

                num[j-] = num[j] - num[j-] + (num[j] = num[j-]);

            }

            if(pos > i)//表示有交换

                ans += (pos-i);

        }

        printf("%d\n",ans);

    }

    return ;

}        

参照:http://blog.csdn.net/lyhvoyage/article/details/12906277