130. Surrounded Regions

题目解读

很类似于围棋将子围起来的规则，当’O’所围成的区域被’X’包围的时候，就将其中的’O’全部换成’X’,否则保留

也就是说如果’O’连接的区域中如果有在棋盘边上的，这块’O’区域就保留。所以确定了这条题目属于搜索类的问题。

思路分析

题目中特殊的点就是在边上的点，所以决定从边上的点开始，找到所有含有边上点的区域，将这些区域中的’O’换个标记，例如：’L’，最后剩余没有替换的’O’换成’X’,’L’还原为’O’。

具体的做法分为深度优先和广度优先两种：

深度优先的代码请参照[LeetCode] Surrounded Regions 包围区域

我自己实现了广度优先的算法，首先是第一版的代码

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
struct point {
	int x;
	int y;
	void operator= (const point& other) {
		x = other.x;
		y = other.y;
	}
};
class Solution {
public:
	void solve(vector<vector<char>>& board) {
		if (board.empty())
		{
			return;
		}
		//BFS 队列
		queue<point> nextTarget;
		//BFS
		for (int i = 0;i < board.size();i++)
		{
			for (int j = 0;j < board[0].size();j++)
			{
				if (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1)
				{
					if (board[i][j] == 'O')
					{
						board[i][j] = 'L';
						if (i - 1 >= 0 && board[i-1][j] == 'O')
						{
							point newTarget;
							newTarget.x = i - 1;
							newTarget.y = j;
							nextTarget.push(newTarget);
						}
						if (i + 1 < board.size() && board[i+1][j] == 'O')
						{
							point newTarget;
							newTarget.x = i + 1;
							newTarget.y = j;
							nextTarget.push(newTarget);
						}
						if (j - 1 >0 && board[i][j-1] == 'O')
						{
							point newTarget;
							newTarget.x = i;
							newTarget.y = j - 1;
							nextTarget.push(newTarget);
						}
						if (j + 1 < board[0].size() && board[i][j+1] == 'O')
						{
							point newTarget;
							newTarget.x = i;
							newTarget.y = j + 1;
							nextTarget.push(newTarget);
						}
						while (!nextTarget.empty())
						{
							point next = nextTarget.front();
							nextTarget.pop();
							board[next.x][next.y] = 'L';
							if (next.x - 1 >= 0 && board[next.x-1][next.y] == 'O')
							{
								point newTarget;
								newTarget.x = next.x - 1;
								newTarget.y = next.y;
								nextTarget.push(newTarget);
							}
							if (next.x + 1 < board.size() && board[next.x + 1][next.y] == 'O')
							{
								point newTarget;
								newTarget.x = next.x + 1;
								newTarget.y = next.y;
								nextTarget.push(newTarget);
							}
							if (next.y - 1 > 0 && board[next.x][next.y-1] == 'O')
							{
								point newTarget;
								newTarget.x = next.x;
								newTarget.y = next.y-1;
								nextTarget.push(newTarget);
							}
							if (next.y+1< board[0].size() && board[next.x][next.y+1] == 'O')
							{
								point newTarget;
								newTarget.x = next.x;
								newTarget.y = next.y+1;
								nextTarget.push(newTarget);
							}
						}
					}
				}
			}
		}
		for (int i = 0;i < board.size();i++)
		{
			for (int j = 0;j < board[0].size();j++)
			{
				if (board[i][j] == 'O')
				{
					board[i][j] = 'X';
				}
				else if (board[i][j] == 'L')
				{
					board[i][j] = 'O';
				}
			}
		}
		return;
	}
};

代码的思路就是以边上的点为起点，广度优先搜索到所有与边上的点连通的’O’，将这些点换成’L’，最后在同一替换。但是这个代码在Oj的稍微复杂的用例时就超出时间。经过对运算过程的分析，发现是上述代码在从一个点添加它上下左右的领接点时，没有改变领接点的状态，这就可能让很多被重复添加到广度优先的搜索队列中造成重复计算，修改之后的代码在PUSH之前先修改了添加进来的点的状态，防止了重复添加

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
struct point {
	int x;
	int y;
	void operator= (const point& other) {
		x = other.x;
		y = other.y;
	}
};
class Solution {
public:
	void solve(vector<vector<char>>& board) {
		if (board.empty())
		{
			return;
		}
		//BFS 队列
		queue<point> nextTarget;
		//BFS
		for (int i = 0;i < board.size();i++)
		{
			for (int j = 0;j < board[0].size();j++)
			{
				if (i == 0 || i == board.size() - 1 || j == 0 || j == board[0].size() - 1)
				{
					if (board[i][j] == 'O')
					{
						board[i][j] = 'L';
						if (i - 1 >= 0 && board[i-1][j] == 'O')
						{
							point newTarget;
							newTarget.x = i - 1;
							newTarget.y = j;
							nextTarget.push(newTarget);
							board[i - 1][j] = 'L';
						}
						if (i + 1 < board.size() && board[i+1][j] == 'O')
						{
							point newTarget;
							newTarget.x = i + 1;
							newTarget.y = j;
							nextTarget.push(newTarget);
							board[i + 1][j] = 'L';
						}
						if (j - 1 >0 && board[i][j-1] == 'O')
						{
							point newTarget;
							newTarget.x = i;
							newTarget.y = j - 1;
							nextTarget.push(newTarget);
							board[i][j-1] = 'L';
						}
						if (j + 1 < board[0].size() && board[i][j+1] == 'O')
						{
							point newTarget;
							newTarget.x = i;
							newTarget.y = j + 1;
							nextTarget.push(newTarget);
							board[i][j + 1] = 'L';
						}
						while (!nextTarget.empty())
						{
							point next = nextTarget.front();
							nextTarget.pop();
							board[next.x][next.y] = 'L';
							if (next.x - 1 >= 0 && board[next.x-1][next.y] == 'O')
							{
								point newTarget;
								newTarget.x = next.x - 1;
								newTarget.y = next.y;
								nextTarget.push(newTarget);
								board[next.x - 1][next.y] = 'L';
							}
							if (next.x + 1 < board.size() && board[next.x + 1][next.y] == 'O')
							{
								point newTarget;
								newTarget.x = next.x + 1;
								newTarget.y = next.y;
								nextTarget.push(newTarget);
								board[next.x + 1][next.y] = 'L';
							}
							if (next.y - 1 > 0 && board[next.x][next.y-1] == 'O')
							{
								point newTarget;
								newTarget.x = next.x;
								newTarget.y = next.y-1;
								nextTarget.push(newTarget);
								board[next.x][next.y - 1] = 'L';
							}
							if (next.y+1< board[0].size() && board[next.x][next.y+1] == 'O')
							{
								point newTarget;
								newTarget.x = next.x;
								newTarget.y = next.y+1;
								nextTarget.push(newTarget);
								board[next.x][next.y + 1] = 'L';
							}
						}
					}
				}
			}
		}
		for (int i = 0;i < board.size();i++)
		{
			for (int j = 0;j < board[0].size();j++)
			{
				if (board[i][j] == 'O')
				{
					board[i][j] = 'X';
				}
				else if (board[i][j] == 'L')
				{
					board[i][j] = 'O';
				}
			}
		}
		return;
	}
};