11C:寻找边缘

总时间限制: 
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数组了,很机智吧!

 

上一篇:LeetCode 79,这道走迷宫问题为什么不能用宽搜呢?


下一篇:UPC-穿越