Life has its own fate, and meeting may not be accidental.

0%

被X包围的区域(BFS)-逆向思维

发表于 更新于 分类于 ，   |   字数统计: 117(字)   |   阅读时长: 1(分) Valine：

寻找被围住的O，可以利用逆向思维，把没围住的找出来，剩下的皆是围住的。之前期末的时候卡了好久

题目

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

输入

输入样例由多组数据组成。第一行输入两个正整数n，m表示边界。（1<=n,m<=100） 接下来输入n*m个'X'和'O'表示矩阵。

输出

输出一个n*m的矩阵表示填充后的矩阵。

样例输入

1
2
3
4
5
4 4
X X X X
X O O X
X X O X
X O X X

样例输出

1
2
3
4
X X X X
X X X X
X X X X
X O X X

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
int n,m,t,zx,zy,flag;
char Map[102][102];
int vis[102][102];
int dir[4][2]={-1,0,0,-1,1,0,0,1};
struct fun{
	int x,y;
}great;
queue<fun> q;
void bfs(){
	while(q.size()){
		fun now=q.front();
		q.pop();
		for(int i=0;i<4;i++){
			int xx=now.x+dir[i][0];
			int yy=now.y+dir[i][1];
			if(xx<0||yy<0||xx>=n||yy>=m){
				continue;
			}
			if(vis[xx][yy]==0&&Map[xx][yy]=='O'){       //讲O标记
				vis[xx][yy]=1;
				great.x=xx;
				great.y=yy;
				q.push(great);
			}
		}
	}
	while(q.size()){
		q.pop();
	}
}
int main(){
	while(scanf("%d %d",&n,&m)!=EOF){
		getchar();
		memset(vis,0,sizeof(vis));
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				scanf("%c",&Map[i][j]);
				getchar();
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
                //讲边缘的标记，里面的不好找，不过边缘联通的一定是不能围住的
				if((i==0||j==0||i==n-1||j==m-1)&&Map[i][j]=='O'){     
					great.x=i;
					great.y=j;
					vis[i][j]=1;
					q.push(great);
					bfs();
				}
			}
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(vis[i][j]==1){
					if(j==0)        //如果被标记肯定是围不住的
						printf("O");
					else
						printf(" O");
				}
				else{               //否则肯定是被围住的
					if(j==0)
						printf("X");
					else
						printf(" X");
				}
			}
			printf("\n");
		}
	}
	return 0;
}