#3958. 寻找边缘

寻找边缘

题目描述:

给定一张 R*C 的地图,由 "X" 和 "O" 组成。

现在需要重新处理这张地图,找到地图边缘的那些 "O"。你需要将这些地图边缘上的 "O" 保留下来,然后将其他的 "O" 全部替换为 "X"。

地图边缘的 "O" 指的是那些处于第一行/列或最后一行/列上的 "O",以及从这些 "O" 的相邻位置(上下左右)延伸出去的 "O"。

输入

第一行是一个正整数 T,表示一共有 T 组数据。 对于每组数据,其第一行是两个正整数 R 和 C,表示地图的大小,用一个空格分开。 接下来的 R 行,每行包含了 C 个字符,分别是 "X" 或 "O"。 其中,0 < T <= 10,0 < R, C <= 500。

输出

对于每组数据,输出 R 行,每行包含了 C 个字符,分别是 "X" 或 "O"。 每组数据之间需要额外输出一个空行。

样例输入

2

2 3

OXX

XXO

5 5

XXXOX

XXXOX

XOOXX

XXOXX

XOXXX

样例输出

OXX

XXO

XXXOX

XXXOX

XXXXX

XXXXX

XOXXX

我的想法

这道题我用的是广搜

输入时先把每个'O'的位置存好(oxy),因为题目要求只留下第一行/列或最后一行/列上的 "O",和从这些 "O" 的相邻位置(上下左右)延伸出去的 "O",所以我们找到第一行/列或最后一行/列上的 "O",并往四周拓展就行了。

Limitation

1s, 1024KiB for each test case. 时间限制:1000

内存限制:65536