摘要：属于构造算法，需要对问题内在的逻辑结构有一定的认识。
题目原地址如下：https://codeforces.com/problemset/problem/1647/B
题目截图如下：
关键词：构造算法，图论，*1200
简要翻译：给予一个01矩阵，其中1代表涂色部分。判断这个网格内是否不含两个相交的极大矩形。
考察该问题的几何特征，我们发现所谓的”相交”即是是否存在”三角形”结构，如果存在即表明存在相交。
代码如下：
1 #include2 #include <string> 3 using namespace std; 4 int k; 5 int m,n; 6 bool ans=false; 7 int rem[300][300]; 8 void solve(int n,int m){ 9 for (int i=1;i){ 10 string med; 11 cin>>med; 12 for (int j=0;j ){ 13 rem[i][j+1]=med[j]-'0'; 14 } 15 } 16 for (int i=1;i1;i++){ 17 for (int j=1;j1;j++){ 18 int judge=rem[i][j]+rem[i+1][j]+rem[i][j+1]+rem[i+1][j+1]; 19 if (judge==3){//小正方形（2*2）内如果想满足“三角形”结构就需要满足和为3 20 cout<<"NO"<<"\n"; 21 return ; 22 } 23 } 24 } 25 cout<<"YES"<<endl; 26 } 27 int main(){ 28 cin>>k; 29 while(k--){ 30 cin>>n>>m; 31 solve(n,m); 32 } 33 return 0; 34 } ();j++
Original: https://www.cnblogs.com/johnsonstar/p/16635973.html
Author: Johnson-Hugo
Title: 学习随笔——codeforces题目Madoka and the Elegant Gift解答
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/583979/
转载文章受原作者版权保护。转载请注明原作者出处！