1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

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]);
            }
        }
    }
};