129_矩阵下三角问题 （2008 round2 A)

 矩阵只能交换相邻行，求化成下三角的最小交换数。

 果断先把第一行换回去（如有多行满足第一行的要求，选择最近的那一行），再换第二行.......

//
//  127_crazy rows.cpp
//  changlle
//
//  Created by user on 1/4/16.
//  Copyright (c) 2016 user. All rights reserved.
//

#include <iostream>
using namespace std;

int N=4;
int M[4][4]={
    {1,1,1,0},
    {1,1,0,0},
    {1,1,0,0},
    {1,0,0,0}
};

int num=0;

int a[4];

int main(){
    
    
    fill (a,a+N,-1);
    
    for (int i=0;i<N;i++){
        
        for (int j=0;j<N;j++){
            if (M[i][j]==0)
            {
                a[i]=j-1;
                break;
            }
        }
        
    }
    
    
    for ( int i=0;i<N;i++) {
        
        int p=-1;
        for (int j=i;j<N;j++) {
            if (a[j]<=i){
                p=j;
               break;
            }
        }
        
    
        for (int j=p;j>i;j--){
            swap(a[j],a[j-1]);
            num++;
        }
 
        
    }
    
    cout<<num<<endl;
    
  
    return 0;
}