大佬30行写出来的东西,硬是给我写了100行,欲哭无泪🥱
大佬写法
这里有一个很奇怪的问题,如果把row和col设置为私有变量,牛客会提示堆栈溢出,但是本地编译器没啥问题。本人才疏学浅,百思不得其姐,求大佬解答
class Solution { public: void solve(vector> &board) { int row = board.size(), col = board[0].size(); if (row < 3 || col < 3) return; // 行 for (int i = 0; i < col; ++i) { dfs(board, 0, i); dfs(board, row - 1, i); } // 列 for (int i = 1; i < row - 1; ++i) { dfs(board, i, 0); dfs(board, i, col - 1); } 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] == '*') board[i][j] = 'O'; } } } void dfs(vector> &board, int i, int j) { if (i board.size() - 1 || j board[0].size() - 1) return; if (board[i][j] == 'O') { board[i][j] = '*'; // 上下左右 dfs(board, i - 1, j); dfs(board, i + 1, j); dfs(board, i, j - 1); dfs(board, i, j + 1); } } };
渣渣写法
class Solution { public: void solve(vector> &board) { // 思路:找出所有开放的点,将剩下的都设为'X' int row = board.size(), col = board[0].size(); if (row <= 2 || col <= 2) return; // 第一行 for (int i = 0; i < col; ++i) { pair loc(0, i); if (board[0][i] == 'O' && !isOpen(loc)) { findO(board, loc); } } // 最后一行 for (int i = 0; i < col; ++i) { pair loc(row - 1, i); if (board[row - 1][i] == 'O' && !isOpen(loc)) { findO(board, loc); } } // 第一列 for (int j = 1; j < row - 1; ++j) { pair loc(j, 0); if (board[j][0] == 'O' && !isOpen(loc)) { findO(board, loc); } } // 最后一列 for (int j = 1; j < row - 1; ++j) { pair loc(j, col - 1); if (board[j][col - 1] == 'O' && !isOpen(loc)) { findO(board, loc); } } // 设置O for (int i = 0; i < row; ++i) { for (int j = 0; j < col; ++j) { pair loc(i, j); if (board[i][j] == 'O' && !isOpen(loc)) { board[i][j] = 'X'; } } } } private: set> openLoc; void findO(vector> &board, pair &loc) { // 借助队列,广度优先遍历 int row = board.size(), col = board[0].size(); queue> record; record.push(loc); openLoc.insert(loc); while (!record.empty()) { pair current = record.front(); record.pop(); // 扫描上下左右,如有O,且没有记录在openLoc中,就推进去 int x = current.first, y = current.second; int top = x - 1; int bottom = x + 1; int left = y - 1; int right = y + 1; loc.first = top; loc.second = y; if (top >= 0 && board[top][y] == 'O' && !isOpen(loc)) { record.push(loc); openLoc.insert(loc); } loc.first = bottom; loc.second = y; if (bottom < row && board[bottom][y] == 'O' && !isOpen(loc)) { record.push(loc); openLoc.insert(loc); } loc.first = x; loc.second = left; if (left >= 0 && board[x][left] == 'O' && !isOpen(loc)) { record.push(loc); openLoc.insert(loc); } loc.first = x; loc.second = right; if (right < col && board[x][right] == 'O' && !isOpen(loc)) { record.push(loc); openLoc.insert(loc); } } } bool isOpen(pair loc) { return !(openLoc.find(loc) == openLoc.end()); } };