简答题 偏难
#7303

寻找边缘 给定一张 R*C 的地图, 由 "X" 和 "O" 组成。 现在需要重新处理这张地图, 找到地图边缘的那些 "O"。 你需要将这些地图边缘上的 "O"…

寻找边缘

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

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

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

时间限制: 1000

内存限制: 65536

输入

第一行是一个正整数 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
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstring&gt; #include &lt;iostream&gt; using namespace std; int r, c; char a[505][505]; int dirx[4] = {0, 0, 1, -1}; int diry[4] = {1, -1, 0, 0}; void dfs(int x, int y) {   for (int i = 0; i &lt; 4; i++) {     int nx = x + dirx[i];     int ny = y + diry[i];     if (a[nx][ny] == 'O') {       a[nx][ny] = '?';       dfs(nx, ny);     }   } } int main() {   int t;   cin &gt;&gt; t;   while (t--) {     memset(a, 0, sizeof(a));     cin &gt;&gt; r &gt;&gt; c;     int i, j;     for (i = 1; i &lt;= r; i++)       for (j = 1; j &lt;= c; j++)         cin &gt;&gt; a[i][j];     for (i = 1; i &lt;= r; i++) {       if (a[i][1] == 'O') {         a[i][1] = '?';         dfs(i, 1);       }       if (a[i][c] == 'O') {         a[i][c] = '?';         dfs(i, c);       }     }     for (i = 1; i &lt;= c; i++) {       if (a[1][i] == 'O') {         a[1][i] = '?';         dfs(1, i);       }       if (a[r][i] == 'O') {         a[r][i] = '?';         dfs(r, i);       }     }     for (i = 1; i &lt;= r; i++) {       for (j = 1; j &lt;= c; j++) {         if (a[i][j] == '?')           cout &lt;&lt; 'O';         else           cout &lt;&lt; 'X';       }       cout &lt;&lt; endl;     }     cout &lt;&lt; endl;   }   return 0; }</pre>
这道题暂未补解析。