TZOJ

TZOJ

3379: 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 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 < m,n < 5)

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

Input is terminated by one line contains two zeros.

输出

If the matrix can be converted into zero, ouput “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

题目来源

中山大学

题目链接：.do?&method=showdetail&id=3379

题目大意:从矩阵中选一个位置，对其和其四周中的一个格子加上一个数字（可以加负数），判断一下是否可以使得矩阵中所有元素的值均为0

这题数据非常的小，开始本来想着dfs搜一下，判断是否可以的，然而后来写的时候发现是存在规律的。

首先求出所有元素和，若是为奇数则一定是不可以的，然后偶数我们模拟一遍过程，这个位置有值，则右边或者下边减去这个数字，最后判断一下右下的数字是否为0

​
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<string.h>
#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;
typedef long long LL;
int a[10][10];
int main(){int n,m;int s;while(scanf("%d%d",&n,&m),n||m){s=0;for(int i=0;i<n;++i){for(int j=0;j<m;++j){scanf("%d",&a[i][j]);s+=a[i][j];s&=1;}}if(s&1){puts("No");}else{for(int i=0;i<n;++i){for(int j=0;j<m;++j){if(a[i][j]){if(j!=m-1){a[i][j+1]-=a[i][j];a[i][j]=0;}else if(i!=n-1){a[i+1][j]-=a[i][j];a[i][j]=0;}}}}if(a[n-1][m-1]){puts("No");}else{puts("Yes");}}}
}​

转载于:.html