A - Crazy Rows SPOJ - HAROWS

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

题目：

You are given an N x N matrix with 0 and 1 values. You can swap any two adjacentrows 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

1 ≤ N ≤ 8

Input	Output
3 2 10 11 3 001 100 010 4 1110 1100 1100 1000	Case #1: 0 Case #2: 2 Case #3: 4

题意：

 给你一个数字T，代表有T组测试数字据；

给你一个数字N，代表是一个N阶矩阵；

后面是一个N阶矩阵；

让你求出来把这个矩阵转换成一个下三角矩阵需要几步？

注意：每次的转换都是交换相邻的两行；

思路：

下三角矩阵：对角线的右上方全是0；

所以在转换之前，我们要清楚每一行的数字的最后一个数字1 在什么位置，然后根据这个位置来确定先把哪一行的位置确定下来；

我们可以由上到下的顺序来完成这个交换：先把第一行的位置确定下来，那么在后面的交换过程中我们就不需要再移动第一行了，节省步骤。那么第一行有什么特点？第一行是全0或者第一个数字是1，后面的全0；题目中保证了，一定有结果，那么我们就可以确定下来移动的顺序了，每一次都是把那一行中最后一个数字1 送在的位置最靠前的移动到最上面没有确定的位置；也就是说把a[ i] 的值小的行逐渐移动到数组的上方；

代码如下：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;const int N=110;int t,n;
char s[N][N];
int map[N][N];
int a[N];//存储每一行中的数字1存在的最后的位置；
int sum;void solve()
{sum=0;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]);//交换；sum++;}}return ;
}int main()
{scanf("%d",&t);int k=0;while(t--){k++;scanf("%d",&n);for(int i=0; i<n; i++)scanf("%s",&s[i]);memset(a,-1,sizeof a);for(int i=0; i<n; i++){for(int j=0; j<n; j++){map[i][j]=s[i][j]-'0';if(map[i][j]==1)a[i]=j;}}solve();printf("Case #%d: %d\n",k,sum);}return 0;
}

 

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

---