LeetCode-Graph-Basic-/130. Surrounded Regions.cpp at master · israkul9/LeetCode-Graph-Basic- · GitHub

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

// DFS from boundary related problem

class Solution {
	int dx[5] = {0, 0, +1, -1};
    int dy[5] = {+1, -1, 0, 0};

	bool visited[200][200];


 void dfs(int x, int y, vector<vector<char>>& graph, int r, int c) {
		 visited[x][y] = true;

		 for (int i = 0; i < 4; i++) {

			 int nowx = dx[i] + x;
			 int nowy = dy[i] + y;
			 if ((nowx >= 0 and nowx < r  and nowy >= 0 and nowy < c)) {
				 if (!visited[nowx][nowy]) {
					 if (graph[nowx][nowy] == 'O')
					 {
						 // bug;

						 graph[nowx][nowy] = '#';

						 dfs(nowx, nowy, graph, r, c);
					 }
				 }
			 }
		 }


	 }

public:
	void solve(vector<vector<char>>& board) {
 ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


        if(board.size()==0)return;

		int row = board.size();
		int col = board[0].size();

		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col ; j++) {
				visited[i][j] = false;
			}
		}


		for (int i = 0; i < row ; i++) {
			for (int j =0 ; j < col ; j++) {
				if (i == 0 and j == 0) {

					if (board[i][j] == 'O' and visited[i][j]==false) {
						dfs(i, j, board, row,col);
						board[i][j] = '#';
					}

					//cout << board[i][j];
				}
				else if (i == 0 and j < col) {
					if (board[i][j] == 'O' and visited[i][j] == false) {
						dfs(i, j, board, row, col);
						board[i][j] = '#';
					}

					//cout << board[i][j];
				}
				else if (i < row and j == 0) {

					if (board[i][j] == 'O' and visited[i][j] == false) {
						dfs(i, j, board, row, col);
						board[i][j] = '#';
					}

					//cout << board[i][j];
				}
				else if (i < row and j == col - 1) {
					if (board[i][j] == 'O' and visited[i][j] == false) {
						dfs(i, j, board, row, col);
						board[i][j] = '#';
					}
					//cout << board[i][j];
				}
				else if (i == row - 1 and j < col) {
					if (board[i][j] == 'O' and visited[i][j] == false) {
						dfs(i, j, board, row, col);
						board[i][j] = '#';
					}
					//cout << board[i][j];
				}

			}
			//cout << endl;

		}


		for (int i = 0; i < row; i++) {
			for (int j = 0; j < col; j++) {

				if (board[i][j] == 'O') board[i][j] = 'X';
				else if (board[i][j] == '#')board[i][j] = 'O';
				cout << board[i][j];

			}
			cout << endl;

		}


	}


};