【codeforces486B】OR in Matrix（思维）

爱被打了一巴掌 2022-07-16 03:12 130阅读 0赞

B. OR in Matrix

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's define logical *OR* as an operation on two logical values (i. e. values that belong to the set \{0, 1\}) that is equal to 1 if either or both of the logical values is set to 1, otherwise it is 0. We can define logical *OR* of three or more logical values in the same manner:

![c471decc0786446790fbddae63ba83c3b84708a9.png][] where ![feab41af979f7136feb6110d94050df54ff9b651.png][] is equal to 1 if some *a**i* = 1, otherwise it is equal to 0.

Nam has a matrix *A* consisting of *m* rows and *n* columns. The rows are numbered from 1 to *m*, columns are numbered from 1 to *n*. Element at row *i* (1 ≤ *i* ≤ *m*) and column *j* (1 ≤ *j* ≤ *n*) is denoted as *A**ij*. All elements of *A* are either 0 or 1. From matrix *A*, Nam creates another matrix *B* of the same size using formula:

![ac9a48831215b05f6775b4d5ef22620151549e9f.png][].

(*B**ij* is *OR* of all elements in row *i* and column *j* of matrix *A*)

Nam gives you matrix *B* and challenges you to guess matrix *A*. Although Nam is smart, he could probably make a mistake while calculating matrix *B*, since size of *A* can be large.

Input

The first line contains two integer *m* and *n* (1 ≤ *m*, *n* ≤ 100), number of rows and number of columns of matrices respectively.

The next *m* lines each contain *n* integers separated by spaces describing rows of matrix *B* (each element of *B* is either 0 or 1).

Output

In the first line, print "NO" if Nam has made a mistake when calculating *B*, otherwise print "YES". If the first line is "YES", then also print *m*rows consisting of *n* integers representing matrix *A* that can produce given matrix *B*. If there are several solutions print any one.

Examples

input

2 2
    1 0
    0 0

output

input

2 3
    1 1 1
    1 1 1

output

YES
    1 1 1
    1 1 1

input

2 3
    0 1 0
    1 1 1

output

YES
    0 0 0
    0 1 0

本题就是先求出A数列，然后求出对应的正确的B，再与所给的实际的B一一对比，如果全都相同则YES，否则错误。

#include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int N = 105;
    int row[N],col[N];
    bool visr[N],visc[N],vis[N][N];
    int a[N][N],d[N][N];
    int main() {
    	int n,m;
    	while(scanf("%d%d",&m,&n)!=EOF) {
    		for(int i=0; i<m; i++) {
    			for(int j=0; j<n; j++) {
    				scanf("%d",&a[i][j]);
    			}
    		}
    		memset(row,0,sizeof(row));
    		memset(col,0,sizeof(col));
    		for(int i=0; i<m; i++) {
    			for(int j=0; j<n; j++) {
    				if(a[i][j]==0) {
    					row[i]=1;
    					col[j]=1;
    				}
    			}
    		}
    		int flag=0;
    		memset(visr,0,sizeof(visr));
    		memset(visc,0,sizeof(visc));
    		for(int i=0; i<m; i++) {
    			for(int j=0; j<n; j++) {
    				if(!row[i]&&!col[j]) {
    					vis[i][j]=1;
    					visr[i]=1;
    					visc[j]=1;
    				}
    			}
    		}
    		memset(d,0,sizeof(d));
    		for(int i=0; i<m; i++) {
    			for(int j=0; j<n; j++) {
    				if(visr[i]||visc[j]) {
    					d[i][j]=1;
    				}
    				if(a[i][j]!=d[i][j]) {
    					flag=1;
    				}
    			}
    		}
    		if(flag) {
    			printf("NO\n");
    			continue;
    		} else {
    			printf("YES\n");
    			for(int i=0; i<m; i++) {
    				for(int j=0; j<n; j++) {
    					if(j==n-1)
    						printf("%d\n",vis[i][j]);
    					else
    						printf("%d ",vis[i][j]);
    				}
    			}
    		}
    	}
    	return 0;
    }

[c471decc0786446790fbddae63ba83c3b84708a9.png]: http://codeforces.com/predownloaded/c4/71/c471decc0786446790fbddae63ba83c3b84708a9.png
[feab41af979f7136feb6110d94050df54ff9b651.png]: /images/20220716/0f5ddc59b9ba497fa841c6c34dc761be.png
[ac9a48831215b05f6775b4d5ef22620151549e9f.png]: /images/20220716/c58b081e4f28488cba286c825ac779f9.png