判断图形是不是一个矩阵
全 1 子矩阵
https://ac.nowcoder.com/acm/contest/1099/A
题目描述：用0，1填充一个n*m的矩型 让你判断全部1是否刚好组成一个矩型
n,m<20;
分析：我的想法是找出最上边最下边最右边最左边的点，如果这些点满足四边形的布局（行和列一 一对应）且面积刚好等于1的个数则是；
另外看到一个解法找到最边界的x1，x2,y3,y4。然后再遍历是否存在0 有则不是；
注意下找点时的技巧
ac代码：
#include<iostream>
using namespace std;
pair<int ,int> pos[4];
int n,m;
void initial(){
pos[0].first=pos[1].second=0x3f3f3f3f;
pos[3].first=pos[2].second=0;
}
int main(){
while(cin>>n>>m){
initial();
int cnt=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char x;
cin>>x;
x-='0';
if(x){
cnt++;
if(i<pos[0].first) pos[0].first=i,pos[0].second=j;
if(i>=pos[3].first) pos[3].first=i,pos[3].second=j;
if(j>pos[2].second) pos[2].first=i,pos[2].second=j;
if(j<=pos[1].second) pos[1].first=i,pos[1].second=j;
}
}
if(cnt==0)cout<<"No"<<endl;
else if(pos[0].first==pos[2].first&&pos[0].second==pos[1].second&&
pos[2].second==pos[3].second&&pos[1].first==pos[3].first&&
cnt==(pos[2].second-pos[0].second+1)*(pos[3].first-pos[2].first+1))
cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
投递美团等公司10个岗位 >