-
Notifications
You must be signed in to change notification settings - Fork 6
/
main.cpp
104 lines (93 loc) · 3.18 KB
/
main.cpp
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
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class MyPoint {
public:
int x;
int y;
MyPoint(int x, int y) : x(x), y(y) {}
};
class Solution {
public:
void solve(vector<vector<char> > &board) {
int rowSize = board.size(), colSize = rowSize > 0 ? board[0].size() : 0;
if (rowSize <= 2 || colSize <= 2) return;
vector<vector<char> > copy = vector<vector<char> >(board.begin(), board.end());
vector<vector<bool> > visited = vector<vector<bool> >(rowSize, vector<bool>(colSize, false));
--rowSize;
--colSize;
queue<MyPoint *> q;
if (copy[0][0] == 'O') {
q.push(new MyPoint(0, 0));
visited[0][0] = true;
}
if (copy[0][colSize] == 'O') {
q.push(new MyPoint(0, colSize));
visited[0][colSize] = true;
}
if (copy[rowSize][0] == 'O') {
q.push(new MyPoint(rowSize, 0));
visited[rowSize][0] = true;
}
if (copy[rowSize][colSize] == 'O') {
q.push(new MyPoint(rowSize, colSize));
visited[rowSize][colSize] = true;
}
for (int i = 1; i < colSize; ++i) {
if (copy[0][i] == 'O')
q.push(new MyPoint(0, i));
if (copy[rowSize][i] == 'O')
q.push(new MyPoint(rowSize, i));
}
for (int i = 1; i < rowSize; ++i) {
if (copy[i][0] == 'O')
q.push(new MyPoint(i, 0));
if (copy[i][colSize] == 'O')
q.push(new MyPoint(i, colSize));
}
for (int i = 1; i < rowSize; ++i)
for (int j = 1; j < colSize; ++j)
board[i][j] = 'X';
MyPoint *tmp;
int dalx[] = {-1, 0, 1, 0}, daly[] = {0, 1, 0, -1};
int x, y;
while (!q.empty()) {
tmp = q.front();
q.pop();
for (int i = 0; i < 4; ++i) {
x = tmp->x + dalx[i];
y = tmp->y + daly[i];
if (x < 1 || y < 1 || x > rowSize || y > colSize)
continue;
if (copy[x][y] == 'O' && !visited[x][y]) {
board[x][y] = 'O';
visited[x][y] = true;
q.push(new MyPoint(x, y));
}
}
delete(tmp);
}
}
};
void out(vector<vector<char> > data) {
for (int i = 0; i < data.size(); ++i) {
for (int j = 0; j < data[i].size(); ++j)
cout << data[i][j];
cout << endl;
}
cout << endl;
}
int main() {
vector<vector<char> > board;
vector<char> b1; b1.push_back('X'); b1.push_back('X'); b1.push_back('X'); b1.push_back('X');
vector<char> b2; b2.push_back('X'); b2.push_back('O'); b2.push_back('O'); b2.push_back('X');
vector<char> b3; b3.push_back('X'); b3.push_back('X'); b3.push_back('O'); b3.push_back('X');
vector<char> b4; b4.push_back('X'); b4.push_back('O'); b4.push_back('X'); b4.push_back('X');
board.push_back(b1); board.push_back(b2); board.push_back(b3); board.push_back(b4);
out(board);
Solution s;
s.solve(board);
out(board);
return 0;
}