还是宽度优先搜索。从边界开始找O,没访问到的O就是被X包围起来的。
struct Pointp { int x; int y; Pointp() : x(0), y(0) {} Pointp(int a, int b) : x(a), y(b) {} }; class Solution { public: int lenm,lenn; int **map; void solve(vector<vector<char>> &board) { lenm = board.size(); if(lenm <= 1)return ; lenn = board[0].size(); map = new int *[lenm]; for(int i = 0;i < lenm;i++) { map[i] = new int[lenn]; } for(int i = 0;i < lenm;i++) { for(int j = 0;j < lenn;j++) { if(board[i][j] == 'O')map[i][j] = 0; else if(board[i][j] == 'X')map[i][j] = 1; } } for(int i = 0;i < lenm;i++) { for(int j = 0;j < lenn;j++) { if((i == 0 || j == 0 || i == lenm-1 || j == lenn-1)&&(map[i][j] == 0)) { map[i][j] = 2; bfs(i,j); } } } for(int i = 0;i < lenm;i++) { for(int j = 0;j < lenn;j++) { if(map[i][j] != 2)board[i][j] = 'X'; } } //for(int i = 0;i < lenm;i++) { // for(int j = 0;j < lenn;j++) { // cout << board[i][j] << ' '; // } // cout << endl; //} } private: void bfs(int x,int y) { int walk[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; vector<Pointp>arr,arrs; arr.clear(); arrs.clear(); Pointp p(x,y); arr.push_back(p); while(true) { arrs.clear(); for(int i = 0;i < arr.size();i++) { for(int j = 0;j < 4;j++) { int x = arr[i].x + walk[j][0]; int y = arr[i].y + walk[j][1]; if((x >= 0 && x <= lenm-1)&&(y >= 0 && y <= lenn-1)&&map[x][y] == 0) { map[x][y] = 2; arrs.push_back(Pointp(x,y)); } } } if(arrs.size() == 0)break; arr.clear(); for(int i = 0;i < arrs.size();i++) { arr.push_back(arrs[i]); } } } };