GCJ--Crazy Rows (2009 Round2 A)

本文主要是介绍GCJ--Crazy Rows (2009 Round2 A)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

You are given an N x N matrix with 0 and 1 values. You can swap any two adjacent rows of the matrix.

Your goal is to have all the 1 values in the matrix below or on the main diagonal. That is, for each X where 1 ≤ X ≤ N, there must be no 1 values in row X that are to the right of column X.

Return the minimum number of row swaps you need to achieve the goal.

Input

The first line of input gives the number of cases, T. T test cases follow.
The first line of each test case has one integer, N. Each of the next N lines contains N characters. Each character is either 0 or 1.

Output

For each test case, output

Case #X: K

where X is the test case number, starting from 1, and K is the minimum number of row swaps needed to have all the 1 values in the matrix below or on the main diagonal.

You are guaranteed that there is a solution for each test case.

Limits

1 ≤ T ≤ 60

Small dataset

1 ≤ N ≤ 8

Large dataset

1 ≤ N ≤ 40

Sample

以下是我的AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX_N 45
using namespace std;
char maze[MAX_N][MAX_N];
int n,temp;
int T;
int a[MAX_N];
void solve()
{int res=0;for(int i=0;i<n;i++){a[i]=-1;for(int j=0;j<n;j++){if(maze[i][j]=='1')a[i]=j;}}for(int i=0;i<n;i++){int pos=-1;for(int j=i;j<n;j++){if(a[j]<=i){pos=j;break;}}for(int j=pos;j>i;j--){swap(a[j],a[j-1]);res++;}}printf("Case #%d: %d\n",temp-T,res);
}
int main()
{//freopen("A-large-practice.in","r",stdin);//freopen("output.out","w",stdout);scanf("%d",&T);temp=T;while(T--){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%s",maze[i]);}solve();}return 0;
}

这篇关于GCJ--Crazy Rows (2009 Round2 A)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---