试题
试题链接
题目描述
Bobo 写了一个 n 行 m 列的矩阵
A
i
,
j
A_{i, j}
Ai,j。 首先，他把所有元素
A
i
,
j
(
1
⩽
i
⩽
n
,
1
⩽
j
⩽
m
)
A_{i, j} (1 \leqslant i \leqslant n, 1 \leqslant j \leqslant m)
Ai,j(1⩽i⩽n,1⩽j⩽m) 设为 0。 然后，他选了 4 个整数
x
1
x_1
x1,
x
2
x_2
x2,
y
1
y_1
y1,
y
2
y_2
y2 满足
1
⩽
x
1
⩽
x
2
⩽
n
,
1
⩽
y
1
⩽
y
2
⩽
m
1 \leqslant x_1 \leqslant x_2 \leqslant n, 1 \leqslant y_1 \leqslant y_2 \leqslant m
1⩽x1⩽x2⩽n,1⩽y1⩽y2⩽m ，并把满足
x
1
⩽
i
⩽
x
2
,
y
1
⩽
j
⩽
y
2
x_1 \leqslant i \leqslant x_2, y_1 \leqslant j \leqslant y_2
x1⩽i⩽x2,y1⩽j⩽y2 的元素
A
i
,
j
A_{i, j}
Ai,j 设为 1。 给出 n 行 m 列的矩阵
A
i
,
j
A_{i, j}
Ai,j , 判断它是否是 Bobo 所写的矩阵。
输入描述
输入文件包含多组数据，请处理到文件结束。 每组数据的第一行包含两个整数 n 和 m. 接下来 n 行，其中第 i 行包含 m 个整数
A
i
,
1
,
A
i
,
2
,
…
,
A
i
,
m
A_{i, 1}, A_{i, 2}, \dots, A_{i, m}
Ai,1,Ai,2,…,Ai,m
1
⩽
n
,
m
⩽
10
1 \leqslant n, m \leqslant 10
1⩽n,m⩽10
A
i
,
j
∈
{
0
,
1
}
A_{i, j} \in \{0, 1\}
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找到，中间必须全部填满1，否则就不是bobo矩阵。
Created with Raphaël 2.2.0
开始
找到最左上角的 1
找到最右下角的 1
中间是不是全是1
输出"Yes"
结束
输出"No"
yes
no
源代码
#include <cstdio>
#include <cstring>
#include <climits>
#include <utility>
using namespace std
;
#define MAX_LENGTH 15
typedef pair
<int, int> COOR
;
bool is_bobo_mat(int n
, int m
, char A
[MAX_LENGTH
][MAX_LENGTH
])
{
COOR upper_leftest_one
= make_pair(INT_MAX
, INT_MAX
);
COOR lower_rightest_one
= make_pair(INT_MIN
, INT_MIN
);
bool found_one
= false;
for (int i
= 0; i
< n
; ++i
)
{
for (int j
= 0; j
< m
; ++j
)
{
if (A
[i
][j
] == '1')
{
found_one
= true;
if (i
< upper_leftest_one
.first
)
upper_leftest_one
.first
= i
;
if (j
< upper_leftest_one
.second
)
upper_leftest_one
.second
= j
;
if (i
> lower_rightest_one
.first
)
lower_rightest_one
.first
= i
;
if (j
> lower_rightest_one
.second
)
lower_rightest_one
.second
= j
;
}
}
}
if (!found_one
)
return false;
for (int i
= upper_leftest_one
.first
; i
<= lower_rightest_one
.first
; ++i
)
{
for (int j
= upper_leftest_one
.second
; j
<= lower_rightest_one
.second
; ++j
)
{
if (A
[i
][j
] == '0')
return false;
}
}
return true;
}
int main()
{
int n
, m
;
char A
[MAX_LENGTH
][MAX_LENGTH
];
while (scanf("%d%d", &n
, &m
) != EOF)
{
memset(A
, 0, sizeof(A
));
for (int j
= 0; j
< n
; ++j
)
scanf("%s", A
[j
]);
if (is_bobo_mat(n
, m
, A
))
puts("Yes");
else
puts("No");
}
return 0;
}
