矩阵归零（Zero Puzzling）

http://oj.acmclub.cn/problems/1026    题目描述

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？

输入描述

A line contains m and n indicating the rows and columns of the matrix(0 Each of the following m lines contains n integers(-10^6<=each integer<=10^6)
Input is terminated by one line contains two zeros.

输出描述

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

样例输入

2 2
1 1
1 0

2 2
0 0
1 1

0 0

样例输出

No
Yes

提示

染色问题

---

.......全英文....... 步骤1.打开有道 2.翻译全篇 3. 回归正题

今日英语单词积累：

matrix：矩阵    element：元素    adjacent：临近的   terminated：终止

You can add a same number to a pair of adjacent elements of the matrix. 

您可以向矩阵的一对相邻元素添加相同的数字。

---

##问题大意及思路

学习至：矩阵归零 - jiu~ - 博客园

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

思路：每个相邻对定是由一黑一白组成。令矩阵中所有白加起来为s1，所有黑加起来为s2。每次 *** 作都会在s1和s2同时加上一个相同的数，因此不会改变s1和s2的差值。故而，要想获得零矩阵，s1与s2的差值一定为0。这是必要条件，那是否充分呢？是的。如果s1=s2，那么我们可以把矩阵所有的数通过 *** 作集中要一个格子p上，假设p为白，那么s2=0，又s1=s2，故而p=0，获得零矩阵。

---

Java实现代码:

import java.util.Scanner;

//矩阵归零
public class Main {
public static void main(String [] args){
	Scanner scanner=new Scanner(System.in);
	//循环输入以00结尾
	while(scanner.hasNextInt()){
		int m=scanner.nextInt();
		int n=scanner.nextInt();
		if(m==0||n==0) break;
		//记录黑白色块上的数值
		int s1=0,s2=0;
		for(int i=1;i<=m;i++){
		   for(int j=1;j<=n;j++){
			   int t=scanner.nextInt();
			   //例如 矩阵1，1 和2，2 不相邻，他们都是白色块，即i+j为偶数
			   //矩阵元素1，2 和2，1也不相邻，他们都是黑色块，即i+j为奇数
			   if((i+j)%2==0) s1=s1+t;
			   else s2=s2+t;							
		   }
		  } 
		//充要条件，s1与s2 相等 ，方可通过相邻方块加减同一个数，使得矩阵变成0矩阵
	    if(s1==s2)    System.out.println("Yes");
	    else   System.out.println("No");
	  
	}
}
}