Homogeneous Squares

发表于 更新于

D - Homogeneous Squares

发表于 2021-01-22

ICPC训练联盟2021冬令营（4）D - Homogeneous Squares

1.题目

Assume you have a square of size n that is divided into n × n positions just as a checkerboard. Two positions (x1, y1) and (x2, y2), where 1 ≤ x1, y1, x2, y2 ≤ n, are called “independent” if they occupy different rows and different columns, that is, x1 ≠ x2 and y1 ≠ y2. More generally, n positions are called independent if they are pairwise independent. It follows that there are n! different ways to choose n independent positions.

Assume further that a number is written in each position of such an n × n square. This square is called “homogeneous” if the sum of the numbers written in n independent positions is the same, no matter how the positions are chosen. Write a program to determine if a given square is homogeneous!

Input

The input contains several test cases.

The first line of each test case contains an integer n (1 ≤ n ≤ 1000). Each of the next n lines contains n numbers, separated by exactly one space character. Each number is an integer from the interval [−1000000, 1000000].

The last test case is followed by a zero.

Output

For each test case output whether the specified square is homogeneous or not. Adhere to the format shown in the sample output.

Sample Input

1
2
3
4
5
6
7
8
2
1 2
3 4
3
1 3 4
8 6 -2
-3 4 0
0

Sample Output

1
2
homogeneous
not homogeneous

2.题目解析

注意for循环，不符合条件是及时跳出循环，否则超时！！！

3.代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <stdio.h>

using namespace std;

int n,a[1009][1009];

int main(){
    while(~scanf("%d",&n),n)
        {
    	for(int i=0;i<n;++i)
    	{
    		for(int j=0;j<n;++j)
    		{
    			scanf("%d",&a[i][j]);
    		}
    	}
    	int flag=1;//判断跳出的标记
    	for(int i=0;i<n-1;++i)//遍历
    	{
    		for(int j=0;j<n-1;++j)
    		{
    			if((a[i][j]+a[i+1][j+1])!=(a[i+1][j]+a[i][j+1]))
    			{
    				flag=0;
    				break;//不符合条件时，直接跳出循环。
    			}
    		}
    		if(!flag) break;
    	}
    	if(!flag) puts("not homogeneous");
    	else puts("homogeneous");
    }
    return 0;
}