2015
04-13

# Graceful Matrix

In Matrix Science, Unit Matrix (UM) is a matrix in which the elements on diagonal are all 1, while others are all 0.
Based on Unit Matrix, we define Basic Matrix and Graceful Matrix:

1.Basic Matrix (BM), BM_i means swap the i-th rows and (i+1)-th rows in the Unit Matrix. (0 based)
2.Graceful Matrix (GM), means in every rows and every columns, there is one and only one 1, while others are all 0.

Now we also have a graceful problem, given a GM whose size is N, you need find a BM sequence. At first, the matrix is a UM, by multiplying the matrix one by one in the BM’s sequence order we can get the GM finally. You needn’t find the shortest sequence, but the sequence’s length can’t exceed the number of elements in GM.

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with an integer N, indicating the GM’s size.
Then N lines follow, each line contains N integers, 1 or 0, indicating the GM.
You can assume the input Matrix is always graceful.

Technical Specification

1. 1 <= T <= 50
2. 2 <= N <= 1000

The first line contains a single integer T, indicating the number of test cases.
Each test case begins with an integer N, indicating the GM’s size.
Then N lines follow, each line contains N integers, 1 or 0, indicating the GM.
You can assume the input Matrix is always graceful.

Technical Specification

1. 1 <= T <= 50
2. 2 <= N <= 1000

3
2
1 0
0 1
2
0 1
1 0
4
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0

Case 1: 0

Case 2: 1
0
Case 3: 2
0 2

#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
int a[1002], b;
vector <int> ans;
int main()
{
int test; scanf("%d", &test);
for (int cas=1; cas<=test; cas++)
{
ans.clear();
int n; scanf("%d", &n);
for (int i=0; i<n; i++)
{
for (int j=0; j<n; j++)
{
scanf("%d", &b);
if (b==1) a[i]=j;
}
}
for (int i=0; i<n; i++)
{
for (int j=i+1; j<n; j++)
{
if (a[j]==i)
{
for (int k=j-1; k>=i; k--)
a[k+1]=a[k], ans.push_back(k);
break;
}
}
a[i]=i;
// for (int j=0; j<n; j++)
// printf("%d ", a[j]);
// putchar(10);
}
printf("Case %d: %d\n", cas, (int)ans.size());
for (int i=0; i<ans.size(); i++)
if (i==ans.size()-1) printf("%d", ans[i]);
else printf("%d ", ans[i]);
putchar(10);
}
return 0;
}