修剪草坪问题有一个n*m的草坪(1
1个回答
假设a[i][j]是需要修剪成的图案的一个点的高度,比如测试样例里面给的矩阵
存在解的条件很简单,任意i,j,存在a[i][j]是第i行或者第j列的最大值
试想一下,如果a[i][j]既不是第i行也不是第j列的最大值,为了剪它必然会破坏i行或者j列.
#include
#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("YESn");
}
else {
printf("NOn");
}
return 0;
}
相关问题
