https://blog.csdn.net/tigerisland45/article/details/54565428
问题描述:
首先输入正整数m和n,分别为矩阵的行和列数,m,n≤30,然后输入m行n列的正整数数据。
将m×n矩阵中行或列连续三个元素同值的变为0。
问题分析:
有各种各样的实现方法。
方法一:
采用一种不使用额外存储的做法,需要消除的元素暂时将其值变为负值,
等行和列都标记之后,再统一消除(置值)为0,最后输出结果。
这种做法编程技巧要高一些,比较锻炼程序员运用技巧的能力。
这种能力许多时候显得十分有用。
方法二:
使用额外的二维数组,用于存储需要消除的元素。
这个做法程序逻辑会更加简洁易懂。付出存储的代价也是有回报的。
程序说明:
方法一:
1.程序中使用了求整数绝对值的数学函数abs(),网上查了一下说使用库math.h有可能有二义性,
应该用stdlib.h来替代,有点吓唬人。也许一些简单的函数自己编写更好。
2.玩程序就是玩时间与空间。这个程序使用了一点技巧,
标记删除元素时,暂时置为负值。
这样做节省了存储空间,但是需要付出一定的时间代价。
程序员需要掌握时间与空间的平衡,采用合理的措施。
3.这个程序逻辑上是简洁的,易于阅读。
4.使用函数memset()对数组进行初始化是套路。
方法二:
就不需要说明什么了,都是简单套路。
题记:
时间与空间是可以交换的,空间与逻辑也是可以交换的。
付出空间的代价,可以换来程序逻辑的简洁。
提交后得100分的C语言程序(方法二)如下:
/* CCF201512-2 消除游戏 */
#include <stdio.h>
#include <string.h>
#define N 30
int a[N][N], t[N][N];
int main(void)
{
int n, m, i, j;
scanf("%d%d", &n, &m);
for(i=0; i<n; i++)
for(j=0; j<m; j++)
scanf("%d", &a[i][j]);
memset(t, 0, sizeof(t));
// 进行行标记(可以消除则置1)
for(i=0; i<n; i++)
for(j=0; j<m-2; j++)
if(a[i][j]== a[i][j + 1] && a[i][j + 1] == a[i][j +2])
t[i][j] = t[i][j + 1] = t[i][j + 2] = 1;
// 进行列标记(可以消除则置1)
for(j=0; j<m; j++)
for(i=0; i<n-2; i++)
if(a[i][j] == a[i + 1][j] && a[i + 1][j] == a[i + 2][j])
t[i][j] = t[i + 1][j] = t[i + 2][j] = 1;
// 重置矩阵a
for(i=0; i<n; i++)
for(j=0; j<m; j++)
if(t[i][j])
a[i][j] = 0;
// 输出结果
for(i=0; i<n; i++) {
for(j=0; j<m; j++) {
if(j != 0)
printf(" ");
printf("%d", a[i][j]);
}
printf("\n");
}
return 0;
}
提交后得100分的C++语言程序(方法一)如下:
/* CCF201512-2 消除游戏 */
#include <iostream>
#include <cmath>
using namespace std;
const int N = 30;
int grid[N][N], n, m;
int main()
{
// 输入数据
cin >> n >> m;
for(int i=0; i<n; i++)
for(int j=0; j<m; j++) {
cin >> grid[i][j];
}
// 进行行标记(可以消除则置为负)
for(int i=0; i<n; i++)
for(int j=0; j<m-2; j++) {
if(abs(grid[i][j]) == abs(grid[i][j+1])
&& abs(grid[i][j+1]) == abs(grid[i][j+2])) {
if(grid[i][j] > 0)
grid[i][j] = - grid[i][j];
if(grid[i][j+1] > 0)
grid[i][j+1] = - grid[i][j+1];
if(grid[i][j+2] > 0)
grid[i][j+2] = - grid[i][j+2];
}
}
// 进行列标记(可以消除则置为负)
for(int j=0; j<m; j++)
for(int i=0; i<n-2; i++) {
if(abs(grid[i][j]) == abs(grid[i+1][j])
&& abs(grid[i+1][j]) == abs(grid[i+2][j])) {
if(grid[i][j] > 0)
grid[i][j] = - grid[i][j];
if(grid[i+1][j] > 0)
grid[i+1][j] = - grid[i+1][j];
if(grid[i+2][j] > 0)
grid[i+2][j] = - grid[i+2][j];
}
}
// 进行清除(可以消除则置为0)并且输出结果
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(grid[i][j] < 0)
grid[i][j] = 0;
if(j != 0)
cout << " ";
cout << grid[i][j];
}
cout << endl;
}
return 0;
}
计算绝对值的数学函数abs()有可能有二义性,自己编写了计算绝对值的函数;
二维数组采用动态化声明(C99等是支持的)。
改进后100分的C++程序(方法一)如下:
/* CCF201512-2 消除游戏 */
#include <iostream>
using namespace std;
inline int myabs(int x)
{
return (x >= 0) ? x : -x;
}
int main()
{
// 输入数据
int n, m;
cin >> n >> m;
int grid[n][m];
for(int i=0; i<n; i++)
for(int j=0; j<m; j++) {
cin >> grid[i][j];
}
// 进行行标记(可以消除则置为负)
for(int i=0; i<n; i++)
for(int j=0; j<m-2; j++) {
if(myabs(grid[i][j]) == myabs(grid[i][j+1]) &&
myabs(grid[i][j+1]) == myabs(grid[i][j+2])) {
if(grid[i][j] > 0)
grid[i][j] = - grid[i][j];
if(grid[i][j+1] > 0)
grid[i][j+1] = - grid[i][j+1];
if(grid[i][j+2] > 0)
grid[i][j+2] = - grid[i][j+2];
}
}
// 进行列标记(可以消除则置为负)
for(int j=0; j<m; j++)
for(int i=0; i<n-2; i++) {
if(myabs(grid[i][j]) == myabs(grid[i+1][j]) && myabs(grid[i+1][j]) == myabs(grid[i+2][j])) {
if(grid[i][j] > 0)
grid[i][j] = - grid[i][j];
if(grid[i+1][j] > 0)
grid[i+1][j] = - grid[i+1][j];
if(grid[i+2][j] > 0)
grid[i+2][j] = - grid[i+2][j];
}
}
// 进行清除(可以消除则置为0)并且输出结果
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(grid[i][j] < 0)
grid[i][j] = 0;
if(j != 0)
cout << " ";
cout << grid[i][j];
}
cout << endl;
}
return 0;
}