题目
分析
题目可以转换成:对每一个在边界上的O开始遍历,标定一篇区域。之后再遍历整个矩阵,没被标定且是O的位置,都应该被填成X。标定区域用bfs和dfs都可以,我这里使用了bfs。
代码
class Solution {
public:
vector<vector<int>> bo;
void solve(vector<vector<char>>& board) {
if (board.empty()){
return;
}
int row = board.size();
int col = board[0].size();
for (int i = 0; i < row; i++){
vector<int> vec;
for (int j = 0; j < col; j++){
vec.push_back(0);
}
bo.push_back(vec);
}
//上边
for (int i = 0; i < col; i++){
if (bo[0][i] == 0 && board[0][i] == 'O'){
bfs(board, 0, i);
}
}
//左边
for (int i = 0; i < row; i++){
if (bo[i][0] == 0 && board[i][0] == 'O'){
bfs(board, i, 0);
}
}
//下边
for (int i = 0; i < col; i++){
if (bo[row - 1][i] == 0 && board[row - 1][i] == 'O'){
bfs(board, row - 1, i);
}
}
//右边
for (int i = 0; i < row; i++){
if (bo[i][col - 1] == 0 && board[i][col - 1] == 'O'){
bfs(board, i, col - 1);
}
}
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++){
if (board[i][j] == 'O' && bo[i][j] == 0){
board[i][j] = 'X';
}
}
}
}
void bfs(vector<vector<char>>& board, int i ,int j){
int next[4][2] = {{0, 1},{0, -1},{1, 0},{-1, 0}};
int row = board.size();
int col = board[0].size();
queue<pair<int,int>> que;
que.push(make_pair(i, j)); //首节点入队
bo[i][j] = 1; //标记首节点
while (!que.empty()){
int cur_i = que.front().first;
int cur_j = que.front().second;
// cout << "当前位置: " << cur_i << " " << cur_j << endl;
que.pop();
for (int m = 0; m < 4; m++){
int next_i = cur_i + next[m][0];
int next_j = cur_j + next[m][1];
// cout << "下一步位置: " << next_i << " " << next_j << endl;
//横坐标合法性检查
if (next_i >= row || next_i < 0){
// cout << "横坐标不合法" << endl;
continue;
}
//纵坐标合法性检查
if (next_j >= col || next_j < 0){
// cout << "纵坐标不合法" << endl;
continue;
}
//是陆地且且没到过
if (board[next_i][next_j] == 'O' && bo[next_i][next_j] == 0){
// cout << "都合法" << endl;
que.push(make_pair(next_i, next_j));
// cnt++; //计数
bo[next_i][next_j] = 1; //标记
}
}
}
}
};
网友评论