google code jam 2009 Problem A. Crazy Rows

google code jam 2009 Problem A. Crazy Rows

題目概述:

給一個正方形01矩陣，請問要交換幾次列，才能使所有1在對角線的左邊。

思路:

將愈近需要交換的交換。

我知道寫得很爛QQ

待補QQ

AC code:

//By SCJ

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

int a[50];

int main()

{

ios::sync_with_stdio(0);

cin.tie(0);

//    freopen("A-small-practice.in","r",stdin);

//    freopen("A-small-practice.out","w",stdout);

   int T;cin>>T;

   for(int no=1;no<=T;++no)

   {

       int n;cin>>n;

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

       {

           a[i]=0;

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

           {

               char tp;cin>>tp;

               if(tp=='1') a[i]=j;

           }

       }

       int ans=0;

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

       {

           int t=i;

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

           {

               if(a[j]<=i) {t=j;break;}

           }

           for(int j=t;j>i;--j) swap(a[j],a[j-1]),ans++;

       }

       cout<<"Case #"<<no<<": "<<ans<<endl;

   }

}