OJ刷题记录：L1-508-围棋(20分)

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void cheakIsland(vector<vector<char>> &matrix, int originX, int originY) {
	const int bx[] = {0, 0, -1, 1};
	const int by[] = {1, -1, 0, 0};
	vector<vector<char>> previous = matrix;
	
	matrix[originX][originY] = 0;
	
	queue<pair<int, int>> q;
	q.emplace(pair<int, int>(originX, originY));
	matrix[originX][originY] = 'X';
	
	int x, y;
	for (; !q.empty();) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			if (x + bx[i] >= 0 && x + bx[i] < matrix.size() && y + by[i] >= 0 && y + by[i] < matrix[0].size()) {
				if (matrix[x + bx[i]][y + by[i]] == 'O') {
					matrix[x + bx[i]][y + by[i]] = 'X';
					q.emplace(pair<int, int>(x + bx[i], y + by[i]));
					if (x + bx[i] == 0 || x + bx[i] == matrix.size() - 1 || y + by[i] == 0 || y + by[i] == matrix[0].size() - 1) {
						matrix = previous;
						return;
					}
				}
			}
		}
	}	
}

int main() {
	int row, column;
	
	cin >> row >> column;

	vector<char> arr(column);
	vector<vector<char>> matrix;
	
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < column; j++) {
			cin >> arr[j];
		}
		matrix.emplace_back(arr);
	}
	
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < column; j++) {
			if (matrix[i][j] == 'O') {
				if (i == 0 || i == matrix.size() - 1 || j == 0 || j == matrix[0].size() - 1) {
					continue;
				}
				cheakIsland(matrix, i, j);
			}
		}
	}
	
	for (int i = 0; i < row; i++) {
		for (int j = 0; j < column; j++) {
			cout << matrix[i][j];
		}
		if (i != row - 1) {
			cout << endl;
		}
	}
	
	return 0;
}