简答题 偏难
#20942

黑白方块 时间限制:1.0 s 内存限制:512.0 MB 题面描述 小杨有一个n行m 列的网格图,其中每个格子要么是白色,要么是黑色。 小杨想知道网格图中是否…

黑白方块

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个n行m 列的网格图,其中每个格子要么是白色,要么是黑色。

小杨想知道网格图中是否存在一个满足如下条件的子矩形:

子矩形由4行4列组成;

子矩形的第1行 和第4行只包含白色格子;

对于子矩形的第2行 和第3行,只有第1个和第4个格子是白色的,其余格子都是黑色的;

请你编写程序帮助小杨判断。

输入格式

第一行包含一个正整数t,代表测试用例组数。

接下来是t组测试用例。对于每组测试用例,一共n+1 行。

第一行包含两个正整数n,m,含义如题面所示。

之后n行,每行一个长度为m的01 串,代表网格图第i行格子的颜色,如果为0,则对应格子为白色,否则为黑色。

输出格式

对于每组测试用例,如果存在,输出 Yes,否则输出 No。


输入样例

3
1 4
0110
5 5
00000
01100
01100
00001
01100
5 5
00000
01100
01110
00001
01100

输出样例

No
Yes
No

满足条件的子矩形形如:

0000
0110
0110
0000

对于全部数据,保证有1≤t≤10,1≤n,m≤100。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; const int N = 110; int w[N][N]; int n,m; int match[4][4]; bool check(int xa,int ya){ for(int i=0;i&lt;4;i++){ for(int j=0;j&lt;4;j++){ if(w[xa+i][ya+j]!=match[i][j]){ return false; } } } return true; } int main(){ int t; cin&gt;&gt;t; for(int i=1;i&lt;3;i++)match[1][i]=match[2][i]=1; while(t--){ cin&gt;&gt;n&gt;&gt;m; for(int i=1;i&lt;=n;i++){ string s; cin&gt;&gt;s; for(int j=1;j&lt;=m;j++){ w[i][j]=s[j-1]-'0'; } } int fl = 0; for(int i=1;i&lt;=n-3;i++){ for(int j=1;j&lt;=m-3;j++){ if(check(i,j)){ fl=1; } } } if(fl)cout&lt;&lt;"Yes\n"; else cout&lt;&lt;"No\n"; } }</pre>
解析

定义二维数组,存储将要输入的网格数据;

将要匹配的模版矩形初始化,4X4的二维数组;

使用循环遍历网格数据中每一个可能的4X4子矩形,检查从位置(i,j)开始的子矩形是否与之前定义好的模版匹配进行判断,输出结果