C++ 解法, 执行用时: 5ms, 内存消耗: 672KB, 提交时间: 2022-01-22
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board char字符型vector<vector<>>
* @return char字符型vector<vector<>>
*/
int row,col;
vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
// write code here
row=board.size();
col=board[0].size();
//将四周的O进行dfs遍历，走过的地方全部变为A
for(int i=0;i<row;i++){
//左右两列
dfs(i,0 ,board);
dfs(i,col-1,board);
}
for(int i=1;i<col-1;i++){
//上下两行
dfs(0 ,i,board);
dfs(row-1,i,board);
}
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(board[i][j]=='X')continue;
if(board[i][j]=='A')board[i][j]='O';
else board[i][j]='X';
}
}
return board;
}
void dfs(int x,int y,vector<vector<char> >& board){
if(x<0||y<0||x==row||y==col||board[x][y]!='O')return;
board[x][y]='A';
dfs(x-1,y,board);
dfs(x+1,y,board);
dfs(x,y+1,board);
dfs(x,y-1,board);
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 784KB, 提交时间: 2022-01-15
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board char字符型vector<vector<>>
* @return char字符型vector<vector<>>
*/
vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
// write code here
int row = board.size();
int col = board[0].size();
for (int i = 0; i < row; ++i) {
if (board[i][0] == 'O') {
dfs(board, i, 0, row, col);
}
if (board[i][col - 1] == 'O') {
dfs(board, i, col - 1, row, col);
}
}
for (int i = 1; i < col; ++i) {
if (board[0][i] == 'O') {
dfs(board, 0, i, row, col);
}
if (board[row - 1][i] == 'O') {
dfs(board, row - 1, i, row, col);
}
}
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
}
if (board[i][j] == 'V') {
board[i][j] = 'O';
}
}
}
return board;
}
private:
void dfs(vector<vector<char>>& board, int x, int y, int row, int col) {
if (x >= row || x < 0 || y >= col || y < 0) {
return;
}
if (board[x][y] == 'O') {
board[x][y] = 'V';
dfs(board, x - 1, y, row, col);
dfs(board, x + 1, y, row, col);
dfs(board, x, y - 1, row, col);
dfs(board, x, y + 1, row, col);
}
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 788KB, 提交时间: 2022-01-27
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board char字符型vector<vector<>>
* @return char字符型vector<vector<>>
*/
int row,col;
vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
row =board.size();
col =board[0].size();
for(int i=0;i<row;i++)
{
dfs(i,0,board);
dfs(i,col-1,board);
}
for(int j=0;j<col;j++)
{
dfs(0,j,board);
dfs(row-1,j,board);
}
for(int i=0;i<row;i++)
{
for(int j=0;j<col;j++)
{
if(board[i][j]=='X')continue;
if(board[i][j]=='A')board[i][j]='O';
else board[i][j]='X';
}
}
return board;
}
void dfs(int x,int y,vector<vector<char> >& board)
{
if(x<0||y<0||x==row||y==col||board[x][y]!='O')return;
board[x][y] = 'A';
dfs(x-1,y,board);
dfs(x+1,y,board);
dfs(x,y+1,board);
dfs(x,y-1,board);
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 792KB, 提交时间: 2021-12-14
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board char字符型vector<vector<>>
* @return char字符型vector<vector<>>
*/
int l1,l2;
// vector<vector<char> > rec;
void dfs(int i,int j,vector<vector<char> >& board){
if(i<0||j<0||i>=l1||j>=l2){
return;
}
if(board[i][j]=='X'|| board[i][j]=='M'){
return;
}
board[i][j]='M';
dfs(i-1,j,board);
dfs(i,j-1,board);
dfs(i+1,j,board);
dfs(i,j+1,board);
}
vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
// write code here
if(board.size()==0||board[0].size()==0)return board;
if(board.size()==1||board[0].size()==1)return board;
l1=board.size();
l2=board[0].size();
// rec=board;
for(int i=0;i<l1;i++){
if(board[i][0]=='O'){
dfs(i,0,board);
}
if(board[i][l2-1]=='O'){
dfs(i,l2-1,board);
}
}
for(int j=0;j<l2;j++){
if(board[0][j]=='O'){
dfs(0,j,board);
}
if(board[l1-1][j]=='O'){
dfs(l1-1,j,board);
}
}
for(int i=0;i<l1;i++){
for(int j=0;j<l2;j++){
if(board[i][j]=='O'){
board[i][j]='X';
}
else if(board[i][j]=='M'){
board[i][j]='O';
}
}
}
return board;
}
};
C++ 解法, 执行用时: 6ms, 内存消耗: 648KB, 提交时间: 2022-04-06
using Pos = pair<int, int>; // (row, column)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param board char字符型vector<vector<>>
* @return char字符型vector<vector<>>
*/
void wfs(vector<vector<char> >& board, Pos startGrid)
{
queue<Pos> gridQue;
int nRows = board.size();
int nCols = board[0].size();
gridQue.push(startGrid);
board[startGrid.first][startGrid.second] = 'K';
while (!gridQue.empty()) {
Pos& grid = gridQue.front();
int row = grid.first;
int col = grid.second;
gridQue.pop();
Pos newGrids[4] = {
{row, col - 1},
{row, col + 1},
{row - 1, col},
{row + 1, col},
};
for (auto g : newGrids) {
if (g.first >= 0 && g.first < nRows &&
g.second >= 0 && g.second < nCols &&
board[g.first][g.second] == 'O') {
gridQue.push(g);
board[g.first][g.second] = 'K';
}
}
}
}
vector<vector<char> > surroundedArea(vector<vector<char> >& board) {
// write code here
int nRows = board.size();
int nCols = board[0].size();
for (int i = 0; i < nRows; i++) {
for (int j = 0; j < nCols; j++) {
if ((i == 0 || i == nRows - 1 || j == 0 || j == nCols - 1) &&
board[i][j] == 'O') {
wfs(board, Pos{i, j});
}
}
}
for (int i = 0; i < nRows; i++) {
for (int j = 0; j < nCols; j++) {
if (board[i][j] == 'K') {
board[i][j] = 'O';
}
else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
return board;
}
};
，矩阵中保证只含有 'X' 和 'O'