修剪草坪问题有一个n*m的草坪(1
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/25 15:22:20
修剪草坪问题有一个n*m的草坪(1
修剪草坪问题
有一个n*m的草坪(1
修剪草坪问题有一个n*m的草坪(1
假设a[i][j]是需要修剪成的图案的一个点的高度,比如测试样例里面给的矩阵
存在解的条件很简单,任意i,j,存在a[i][j]是第i行或者第j列的最大值
试想一下,如果a[i][j]既不是第i行也不是第j列的最大值,为了剪它必然会破坏i行或者j列.
#include <stdio.h>
#define max(a,b) (a>b?a:b)
int maxrow[110], maxcol[110];
int a[110][110];
int main () {
int n , m;
scanf("%d %d", &n, &m);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
scanf("%d", &a[i][j]);
maxrow[i] = max(a[i][j],maxrow[i]);
maxcol[j] = max(a[i][j],maxcol[j]);
}
}
bool isok = true;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (maxrow[i] > a[i][j] && maxcol[j] > a[i][j]) {
isok = false;
}
}
}
if (isok) {
printf("YES\n");
}
else {
printf("NO\n");
}
return 0;
}