题目描述:用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; } }