CF #420 A. Okabe and Future Gadget Laboratory

向右看齐 2022-06-13 06:27 127阅读 0赞

A. Okabe and Future Gadget Laboratory

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Okabe needs to renovate the *Future Gadget Laboratory* after he tried doing some crazy experiments! The lab is represented as an *n* by *n* square grid of integers. A *good* lab is defined as a lab in which every number not equal to 1 can be expressed as the sum of a number in the same row and a number in the same column. In other words, for every *x*, *y* such that 1 ≤ *x*, *y* ≤ *n* and *a**x*, *y* ≠ 1, there should exist two indices *s* and *t* so that *a**x*, *y* = *a**x*, *s* + *a**t*, *y*, where *a**i*, *j* denotes the integer in *i*\-th row and *j*\-th column.

Help Okabe determine whether a given lab is *good*!

Input

The first line of input contains the integer *n* (1 ≤ *n* ≤ 50) — the size of the lab.

The next *n* lines contain *n* space-separated integers denoting a row of the grid. The *j*\-th integer in the *i*\-th row is *a**i*, *j* (1 ≤ *a**i*, *j* ≤ 105).

Output

Print "Yes" if the given lab is *good* and "No" otherwise.

You can output each letter in upper or lower case.

Examples

input

3
    1 1 2
    2 3 1
    6 4 1

output

Yes

input

3
    1 5 2
    1 1 1
    1 2 3

output

Note

In the first sample test, the 6 in the bottom left corner is valid because it is the sum of the 2 above it and the 4 on the right. The same holds for every number not equal to 1 in this table, so the answer is "Yes".

In the second sample test, the 5 cannot be formed as the sum of an integer in the same row and an integer in the same column. Thus the answer is "No".

思路：循环每个非1数，然后同行 同列进行判定，注意跳过比自己大的数  和自己

#include<iostream>
    #include<cstdio>
    #define maxn 55 
    int N;
    int a[maxn][maxn];
    using namespace std;
    int chark(int n, int m, int index) {  //以这个数为中心，横竖行进行循环 
    	for(int i = 1; i <= N; i++) {
    		if(a[i][m] >= index || i == n)  //如果此列中 循环到比此数大的话 跳过 循环到自己跳过 
    			continue;
    		for(int j = 1; j <= N; j++) {
    			if(a[n][j] >= index || j == m)  //同上 
    				continue;
    			if(a[i][m] + a[n][j] == index)  //判定是否成功 
    				return 1;
    		}
    	}
    	return 0;
    }
    int main () {
    	scanf("%d", &N);
    	for(int i = 1; i <= N; i++) 
    		for(int j = 1; j <= N; j++) 
    			scanf("%d", &a[i][j]); //输入二维数组中 
    			
    	for(int i = 1; i <= N; i++) {
    		for(int j = 1; j <= N; j++) {
    			if(a[i][j] != 1) {  //如果是1 的话跳过 
    				int index = chark(i, j, a[i][j]);
    				if(index == 0) {  //有一个不符合直接结束 
    					printf("No\n");
    					return 0;	
    				}
    			}
    		}
    	}
    	printf("Yes\n");
    	return 0;
    }