首页 > 代码库 > UVA - 12036 Stable Grid

UVA - 12036 Stable Grid

2024-07-17 17:34:17   216人阅读

Description

Download as PDF


 Stable Grid 

Consider a grid of size n x n where each cell contains a number. Let‘s call a grid stable if we canrearrange the numbers of each row so that every column of the resulting grid has no repeated values.

Mathematically, say, we have a grid G of sizen x n. We would like to permute the elements of eachrowGi (1$ \le$i$ \le$n) so that the resulting grid has the following property:

For every column j, the valuesGi, j are all distinct for (1$ \le$i$ \le$n).

As an example, consider a grid G of size 4 x 4 as shown below

2113 
3126 
26103 
9876 

We can permute each row to get G‘ as shown below

2113 
1362 
62310 
9876 

In G‘, there are no repeated values in any column. So, the given grid is stable.

In this problem, you will be given a grid of size nx n and you have to determine whether it is stableor not.

Input

Input starts with an integer T ($ \le$500), denoting the number of test cases.

Each case starts with a line containing the value of n (0 <n < 100). The next n lines containnintegers each. The j-th integer of thei-th line represent the value of Gi, j. Consecutive integers in eachline are separated with space characters. All the integers in the grid are non-negative with magnitudenot greater than 100.

Output

For each case, output the case number first. If the given grid is stable, output `yes‘ otherwise output`no‘. Look at the samples for exact format.

Sample Input

3
4
2 1 1 3
3 1 2 6
2 6 10 3
9 8 7 6
3
1 1 2
1 1 1
2 2 2
3
1 2 3
2 3 1
3 1 2

Sample Output

Case 1: yes
Case 2: no
Case 3: yes
题意：给定一个矩阵，是否可以对每行进行重排，使得每列的所有元素各不相同思路：记录一个数出现的次数，大于n的话，那么无论怎么排都会有重复
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;

int vis[maxn], n;

int main() {
	int t, cas = 1;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		memset(vis, 0, sizeof(vis));
		int a;
		int flag = 0;
		for (int i = 0; i < n; i++) 
			for (int j = 0; j < n; j++) {
				scanf("%d", &a);	
				vis[a]++;
				if (vis[a] > n) 
					flag = 1;
			}
		printf("Case %d: ", cas++);	
		if (flag) 
			printf("no\n");
		else printf("yes\n");

	}
	return 0;
}


联系
我们