题意:有你一个草坪,草的初始高度都是100,让你用割草机割,割草机只能横着或竖着割,每次割的高度一定,问你能不能割出给定的草坪出来。

考虑任意一个草被割要么是横着要么竖着,所以任意一个草必然是它所在行或列里面高度最大(或相等)的,因此如果存在一个草在它所在的行和列里都不是最大的则无法割出给定的草坪。

/*
* this code is made by wangzhili
* Problem: 1044
* Verdict: Accepted
* Submission Date: 2014-08-08 20:30:21
* Time: 12MS
* Memory: 1724KB
*/
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int mat[111][111];
int main(){
int t, n, m;
scanf("%d", &t);
for(int CASE = 1;CASE <= t; CASE ++){
scanf("%d%d", &n, &m);
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++) scanf("%d", &mat[i][j]);
}
int flag = 0;
for(int i = 0;i < n;i ++){
for(int j = 0;j < m;j ++){
int cnt = 0;
for(int k = 0;k < m;k ++){
if(mat[i][j] < mat[i][k]){
cnt ++;
break;
}
}
for(int k = 0;k < n;k ++){
if(mat[i][j] < mat[k][j]){
cnt ++;
break;
}
}
if(cnt == 2){
flag = 1;
break;
}
}
if(flag) break;
}
printf("Case #%d: ", CASE);
if(flag) printf("NO\n");
else printf("YES\n");
}
return 0;
}
05-11 13:57