2019湖南“强智杯”省赛A题

A. 全 1 子矩阵

Bobo 写了一个 n 行 m 列的矩阵 Ai,j. • 首先，他把所有元素 Ai,j (1≤ i ≤ n,1≤ j ≤ m) 设为 0. • 然后，他选了 4 个整数 x1,x2,y1,y2 满足 1 ≤ x1 ≤ x2 ≤ n,1 ≤ y1 ≤ y2 ≤ m，并把满足 x1 ≤ i ≤ x2,y1 ≤ j ≤ y2 的元素 Ai,j 设为 1. 给出 n 行 m 列的矩阵 Ai,j, 判断它是否是 Bobo 所写的矩阵。

输入格式

输入文件包含多组数据，请处理到文件结束。 每组数据的第一行包含两个整数 n 和 m. 接下来 n 行，其中第 i 行包含 m 个整数 Ai,1,Ai,2,…,Ai,m. • 1≤ n,m ≤10 • Ai,j ∈{0,1} • 至多 1000 组数据。

输出格式

对于每组数据，如果所给矩阵是 Bobo 所写的矩阵，输出 Yes, 否则输出 No.

样例输入

2 2
11
10
3 3
000
001
000
3 4
1111
1111
1111

样例输出

No
Yes
Yes

本题属于省赛中的水题，思路在于扫描矩阵后，找到1的行列对应的最小值和最大值，然后在这个对应的行列式中继续扫描，若出现0则输出No，反之若全为1则输出Yes。

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std
char vis[15][15]
int main()
{
	int n, m
	while (scanf("%d %d",&n,&m)!=EOF)
	{
		int flag = 0
		int l1, l2, r1, r2
		l1 = r1 = 15
		l2 = r2 = 0
		for(int i=1i<=ni++)
			for (int j = 1 j <= m j++)
			{
				cin >> vis[i][j]
				if (vis[i][j] == '1')
				{
					if (i < l1)
						l1 = i
					if (i > l2)
						l2 = i
					if (j < r1)
						r1 = j
					if (j > r2)
						r2 = j
				}
			}
        if(l2<l1||r2<r1)
        {
            flag=1
            cout << "No" << endl
        }
        else
        {
		    for(int i=l1i<=l2&&!flagi++)
            {
                for(int j=r1j<=r2j++)
			    	if (vis[i][j] == '0')
			    	{
				    	flag = 1
				    	cout << "No" << endl
				    	break
				    }
            }
		    if (flag==0)
			    cout << "Yes" << endl
        }
	}
	return 0
}