济宁市网站建设_网站建设公司_HTTPS_seo优化

一、题目描述

二、算法原理

1）处理边缘 'O'，防止干扰微软 'O' ：

2）使用层序遍历查找中间的使用的 'O' 并且让他变成 '1'：

https://blog.csdn.net/2403_84958571/article/details/157102889?spm=1011.2415.3001.10575&sharefrom=mp_manage_link

3）在查找围绕'0'，之后最后再把 '1' 变成 ‘O’

三、代码实现

class Solution { int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; typedef pair<int,int> PII; public: void solve(vector<vector<char>>& board) { for(int i = 0; i < board.size();i++)//处理 第 1 行 和 最后 1 行的边界情况，边界 'O' = '1',防止干扰围绕的 'O' { if(i == 0 || i == board.size() - 1) { for(int k = 0; k <board[0].size(); k++) { if(board[i][k] == 'O') { board[i][k] = '1'; become(board,i,k); } } } } for(int i = 1; i < board.size() - 1; i++)//处理中间行的边界情况,边界 'O' = '1' { for(int k = 0; k < board[0].size();k++) { if(k == 0 || k == board[0].size() - 1) { if(board[i][k] == 'O') { board[i][k] = '1'; become(board,i,k); } } } } for(int i = 0; i < board.size(); i++)//查找中间 'O' { for(int k = 0; k < board[0].size(); k++) { if(board[i][k] == 'O') { board[i][k] = 'X'; CheckBoard(board,i,k); } if(board[i][k] == '1')//还原 '1' = 'O' { board[i][k] = 'O'; } } } } void CheckBoard(vector<vector<char>>& board,int i,int k) { queue<PII> que; que.push({i,k}); while(que.size()) { auto [x,y] = que.front(); que.pop(); for(int a = 0; a < 4; a++) { int new_x = x + dx[a]; int new_y = y + dy[a]; if(new_x >= 0 && new_x < board.size() && new_y >= 0 && new_y < board[0].size() && board[new_x][new_y] == 'O') { board[new_x][new_y] = 'X'; que.push({new_x,new_y}); } } } } void become(vector<vector<char>>& board,int i,int k) { queue<PII> que; que.push({i,k}); while(que.size()) { auto [x,y] = que.front(); que.pop(); for(int a = 0; a < 4; a++) { int new_x = x + dx[a]; int new_y = y + dy[a]; if(new_x >= 0 && new_x < board.size() && new_y >= 0 && new_y < board[0].size() && board[new_x][new_y] == 'O') { board[new_x][new_y] = '1'; que.push({new_x,new_y}); } } } } };