矩阵归零

题目：

zero puzzling

There is a matrix with m rows and n columns. An element of the matrix has at most four adjacent elements(up, down, left, right). You can add a same number to a pair of adjacent elements of the matrix. By doing this operation repeatedly, can you make the matrix zero?

Input:

　　A line contains m and n indicating the rows and columns of the matrix. (0<m,n<5)

　　Each of the following m lines contains n integers(-10^6<=each integer<=10^6).

　　Input is terminated by one line contains two zeros.

Output:

　　If the matrix can be converted into zero, output "Yes" on a line otherwise output "No" on a line.

Sample Input:

2    2
1    1
1    0

2    2
0    0
1    1

0    0

Sample Output:

No
Yes

题意：给定一个m行n列的数字矩阵，问能否通过反复使用给定的操作，使得最终矩阵里的所有数字都为0.题目允许的操作是对矩阵中某对相邻数都加上同一个数值。

思路：对于4*4的矩阵，总共有24对相邻对。由于加的数值未知，搜索会超时。方法得另想。我们可以把间隔的格子分别染成黑白两色，把矩阵搞得如国际象棋棋盘一般。这样染色后，每个相邻对定是由一黑一白组成。令矩阵中所有白加起来为s1，所有黑加起来为s2。每次操作都会在s1和s2同时加上一个相同的数，因此不会改变s1和s2的差值。故而，要想获得零矩阵，s1与s2的差值一定为0。这是必要条件，那是否充分呢？是的。如果s1=s2，那么我们可以把矩阵所有的数通过操作集中要一个格子p上，假设p为白，那么s2=0，又s1=s2，故而p=0，获得零矩阵。集中的方法：设第一行为a,b,c，那么(a,b)同时加上-a，则为(0,b-a)，同理(b-a,c)->(0,c-b+a)，同理一直这样下去，直到最后的格子上，即获得零矩阵。根据以上分析，充要条件即为s1==s2。时间复杂度为O(mn)。

代码：

#include<iostream>
#include<cstdio>
using namespace std;

int main(){
    int m,n;
    while(scanf("%d%d",&m,&n),m||n){
        int s1=0,s2=0;
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++){
                int t;
                scanf("%d",&t);
                if((i+j)&1)    s1+=t;
                else    s2+=t;
            }
        if(s1==s2)    puts("Yes");
        else    puts("No");
    }
    return 0;
}