程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CF#277 (Div. 2) B.(Ô¤´¦Àí)

CF#277 (Div. 2) B.(Ô¤´¦Àí)

編輯：C++入門知識

CF#277 (Div. 2) B.(Ô¤´¦Àí)

B. OR in Matrix time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output ÌâÄ¿Á´½Ó£ºhttp://codeforces.com/contest/486/problem/B

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:

$\$ where $\$ is equal to 1 if some ai?=?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 Aij. All elements of A are either 0 Z†·Ÿ"http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vciAxLiBGcm9tIG1hdHJpeCA8ZW0+QTwvZW0+LAogTmFtIGNyZWF0ZXMgYW5vdGhlciBtYXRyaXggPGVtPkI8L2VtPiBvZiB0aGUgc2FtZSBzaXplIHVzaW5nIGZvcm11bGE6PC9wPgo8cD4KPGltZyBhbGlnbj0="middle" class="tex-formula" src="http://www.bkjia.com/uploads/allimg/141115/04045L1a-2.png" alt="\">.

(Bij 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 mrows consisting of n integers representing matrix A that can produce given matrix B. If there are several solutions print any one.

Sample test(s) input

2 2
1 0
0 0

output

NO

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

½âÌâË¼Â·£º

	ÌâÄ¿´óÒâ¾ÍÊÇ¸øÄãmºÍn£¬½ÓÏÂÀ´ÊäÈëm*nµÄB¾ØÕó£¬ÎÊÊÇ·ñ´æÔÚÒ»¸öm*nµÄA¾ØÕó£¬Ê¹µÃ¶ÔÓÚBijÕâ¸öÔªËØÀ´Ëµ£¬ËüÊÇÓÉA¾ØÕóµÄµÚiÐÐËùÓÐÔªËØºÍµÚjÁÐËùÓÐÔªËØ¡°»òÔËËã¡±µÃÀ´¡£´æÔÚµÄ»°Êä³öYES£¬²¢Êä³öÈÎÒâÒ»×é·ûºÏÌõ¼þµÄA¾ØÕó£¬·ñÔòÊä³öNO¡£

	ÎÒµÄ·½·¨»¹ÊÇÆ«±©Á¦£¬Ê×ÏÈ¿ªÒ»¸ö¶þÎ¬Êý×é´æA¾ØÕó£¬²¢¶ÔÆä³õÊ¼»¯ÔªËØÈ«Îª1¡£Ê×ÏÈÕâÑù¿¼ÂÇ£¬Èç¹ûBij¶ÔÓ¦µÄ值Îª0£¬ÄÇÃ´A¾ØÕóµÄµÚiÐÐºÍµÚjÁÐÒ»¶¨È«²¿Îª0£¬³öÏÖÒ»¸ö1¶¼²»ÐÐ£¬ÒòÎª¡°»òÔËËã¡±È«0³ö0¡£ÕâÑù¸üÐÂÒ»±éºó£¬A¾ØÕóµÄ0µÄÎ»ÖÃ¾ÍÄÜÈ«²¿È·¶¨ÁË¡£½ÓÏÂÀ´×î±©Á¦µÄ²¿·ÖO£¨n*m*max(n,m)£©µÄÅÐ¶ÏA¾ØÕóÃ¿¸öÎ»ÖÃµÄÔªËØÊÇ·ñÂú×ãB¾ØÕóÖÐ0»ò1µÄÌõ¼þ¡£×îºóflagÃ»±äµÄ»°£¬ËµÃ÷´æÔÚÕâÑùµÄA¾ØÕó£¬Í¬Ê±A¾ØÕóÒ²±»ÎÒÃÇ¸üÐÂºÃÁË£¬Êä³ö¼´¿É£»·´Ö®£¬²»´æÔÚÊä³öNO¡£

ÍêÕû´úÂë£º

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#pragma comment(linker, "/STACK:102400000,102400000")

typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;

/** Constant List .. **/ //{

const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;
int n , m;
int g[1111][1111];
int res[1111][1111];



bool check_0(int x , int y)
{
    for(int i = 0 ; i < m ; i ++)
    {
        if(res[x][i] == 1)
            return false;
    }
    for(int i = 0 ; i < n ; i ++)
    {
        if(res[i][y] == 1)
            return false;
    }
    return true;
}


bool check_1(int x , int y)
{
    for(int i = 0 ; i < m ; i ++)
    {
        if(res[x][i] == 1)
            return true;
    }
    for(int i = 0 ; i < n ; i ++)
    {
        if(res[i][y] == 1)
            return true;
    }
    return false;
}

int main()
{
    #ifdef DoubleQ
    freopen("in.txt","r",stdin);
    #endif
    while(~scanf("%d%d",&m,&n))
    {
        for(int i = 0 ; i < m ; i ++)
        {
            for(int j = 0 ; j < n ; j ++)
            {
                scanf("%d",&g[i][j]);
            }
        }
        for(int i = 0 ; i < m ; i ++)
        {
            for(int j = 0 ; j < n ; j ++)
            {
                res[i][j] = 1;
            }
        }
        //int flag = 0 ;
        for(int i = 0 ; i < m ; i ++)
        {
            for(int j = 0 ; j < n ; j ++)
            {
                if(g[i][j] == 0)
                {
                    for(int k = 0 ; k < n ; k ++)
                        res[i][k] = 0;
                    for(int k = 0 ; k < m ; k ++)
                        res[k][j] = 0;
                }
            }
        }
        int flag1 = 0;
        for(int i = 0 ; i < m ; i ++)
        {
            for(int j = 0 ; j < n ; j ++)
            {
                if(g[i][j] == 0)
                {
                    if(!check_0(i , j))
                        flag1 = 1;
                }
                else if(g[i][j] == 1)
                {
                    if(!check_1(i , j))
                        flag1 = 1;
                }
                if(flag1)
                    break;
            }
            if(flag1)
                break;
        }
        if(flag1)
            printf("NO\n");
        else
        {
            printf("YES\n");
            for(int i = 0  ; i < m  ; i ++)
            {
                for(int j = 0 ; j < n ; j ++)
                {
                    printf("%d%c",res[i][j], j == n - 1 ? '\n' : ' ');
                }
            }
        }


    }
}

上一頁:Uva 590 Always on the run （Dp）
下一頁:(每日算法)Leetcode--Simplify Path (簡單路徑)

閱讀排行榜

stl的實現原理簡單講解，通熟易懂，stl原理講解 SDUT OJ 數據結構實驗之棧四：括號匹配 C++ 頭文件相互包含的問題 std::for_each，stdfor_each 講述C語言編寫Windows服務程序 hdu 3816 To Be NUMBER ONE 一道數論主要是思路 Unique Paths II -- LeetCode 【LeetCode從零單刷】Search a 2D Matrix 經典算法——數組中的逆序對二叉排序樹（c++實現）數據結構Spaly_Tree

熱門圖文

php獲取用戶IPv4或IPv6地址的代碼 C#難點逐個擊破(6)：C#數據類型與.net framework數據類型解決Hibernate原生SQL映射問題解析ABP框架領域層中的實體類與倉儲類 J2ME：定時器(TimerTask)使用及初探 java-初學Java，編寫的一段小程序，運行結果有點問題，檢查多時未果，求大家指導？聊天室php&mysql(五) PHP禁止頁面緩存輸出

欄目導航

C++基礎知識 C++入門知識關於C++