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

0%

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

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

题目

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

输入

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

输出

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

样例输入

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

样例输出

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

代码

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