首页 > ACM题库 > HDU-杭电 > HDU 3821-Graceful Matrix[解题报告]HOJ
2015
04-13

HDU 3821-Graceful Matrix[解题报告]HOJ

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;
}