- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
给定一张 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
1 #include<iostream>
2 #include<cstring>
3 using namespace std;
4 int r, c;
5 char a[505][505];
6 int dirx[4] = {0,0,1,-1};
7 int diry[4] = {1,-1,0,0};
8 void dfs(int x, int y){
9 for(int i = 0; i < 4; i++){
10 int nx = x+dirx[i];
11 int ny = y+diry[i];
12 if(a[nx][ny]=='O'){
13 a[nx][ny] = '?';
14 dfs(nx, ny);
15 }
16 }
17 }
18 int main(){
19 int t;
20 cin>>t;
21 while(t--){
22 memset(a,0,sizeof(a));
23 cin>>r>>c;
24 int i, j;
25 for(i = 1; i <= r; i++)
26 for(j = 1; j <= c; j++)
27 cin>>a[i][j];
28 for(i = 1; i <= r; i++){
29 if(a[i][1]=='O'){
30 a[i][1] = '?';
31 dfs(i, 1);
32 }
33 if(a[i][c]=='O'){
34 a[i][c] = '?';
35 dfs(i, c);
36 }
37 }
38 for(i = 1; i <= c; i++){
39 if(a[1][i]=='O'){
40 a[1][i] = '?';
41 dfs(1, i);
42 }
43 if(a[r][i]=='O'){
44 a[r][i] = '?';
45 dfs(r, i);
46 }
47 }
48 for(i = 1; i <= r; i++){
49 for(j = 1; j <= c; j++){
50 if(a[i][j]=='?')cout<<'O';
51 else cout<<'X';
52 }
53 cout<<endl;
54 }
55 cout<<endl;
56 }
57 return 0;
58 }
备注：收获是复制粘贴要谨慎！别忘了改！ （WA两次的原因）
用了比较取巧的办法，就是先把边缘的O暂时用?替代，这样就跟内部的O区别开，处理起来很方便，也不用visited数组了，很机智吧！