九度oj 题目1250：矩阵变换

题目描述：: 对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右）某一个元素也加一，
现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。

输入：

输出：: 如果可以变换得到输出"Yes"，否则"No"。
存在多组数据，每组数据第一行一个正整数n(n<=10),表示一个n*n的矩阵，然后紧跟n行，每行n个整数。当n为0时，测试结束。

样例输入：

样例输出：

Yes
No

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <iostream>
 6 #include <cmath>
 7 int matrix[12][12];
 8 int dir[][2] = {{0,1},{0,-1},{1,0},{-1,0}};
 9 
10 int main(int argc, char const *argv[])
11 {
12     int n;
13     while(scanf("%d",&n) != EOF && n != 0)  {
14         int x = 0, y = 0;
15         for(int i = 0; i < n; i++) {
16             for(int j = 0; j < n; j++) {
17                 scanf("%d",&matrix[i][j]);
18                 if((i + j) & 1) {
19                     x = x + matrix[i][j];
20                 }
21                 else {
22                     y = y + matrix[i][j];
23                 }
24             }
25         }
26         if(x != y) {
27             puts("No");
28             continue;
29         }
30         bool isOk = true;
31         for(int i = 0; i < n && isOk; i++) {
32             for(int j = 0; j < n && isOk; j++) {
33                 int sum = 0;
34                 for(int p = 0; p < 4; p++) {
35                     int tmpx = i + dir[p][0];
36                     int tmpy = j + dir[p][1];
37                     if(tmpx >= 0 && tmpx < n && tmpy >= 0 && tmpy < n) {
38                         sum = sum + matrix[tmpx][tmpy];
39                     }
40                 }
41                 if(matrix[i][j] > sum) {
42                     isOk = false;
43                     break;
44                 }
45             }
46         }
47         if(isOk) {
48             puts("Yes");
49         }
50         else {
51             puts("No");
52         }
53 
54 
55     }
56     return 0;
57 }

这道题关键是找到判断的充要条件，这里的充要条件有两个（摘自http://www.cnblogs.com/liangrx06/p/5083814.html），

（1）X=sum(A[i][j]其中i+j是奇数,Y=sum(A[i][j])其中i+j是偶数,则有X=Y
（2）任意一个元素不大于周围四个元素的和