Surrounded Regions

题目描述
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
 

Complete code：

// xxxOOO.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
using namespace std;
char board[201][201];
int book[201][201];
int n, m;
void dfs(int x, int y) {
	int i, j, k,tx,ty;
	//四个方向 右下左上
	int next[4][2] = {
		{0,1},{1,0},{0,-1},{-1,0}
	};

	for (k = 0;k < 4;k++) {
		tx = x + next[k][0];//新坐标
		ty = y + next[k][1];
		//判断边界 出界退出
		if (tx < 1 || tx > n || ty < 1 || ty > m)
			continue;
		//如果当前是O才判断 如果是X直接跳过
		if (board[x][y] == 'O') {
			//如果下一个点也是O说明两者有连接 直接将当前点翻转为X
			if (board[tx][ty] == 'O'&&book[tx][ty]==0) {
				book[tx][ty] = 1;
				board[x][y] = 'X';
				dfs(tx, ty);
			}
			//如果下一个点是X，即需要判断当前点的四周是否都是X，如果都是那么也将其翻转，如果四周有O那么将当前点翻转
			if (board[tx][ty] == 'X'&&book[tx][ty] == 0) {
				book[tx][ty] = 1;
				if (k ==2){
					board[x][y] ='X';
					return;
				}
				dfs(x, y);
				
			}
		}
	}
	return;
}
int main()
{
	int i, j;
	cin >> n >> m;
	//输入数据
	for (i = 1;i <= n;i++)
		for (j = 1;j <= m;j++)
			cin >> board[i][j];
	//除了四周的点都进行带入
	for(i=2;i<n-1;i++)
		for(j=2;j<m-1;j++)
			dfs(i, j);//进入
	cout << endl;
	//输出矩阵
	for (i = 1;i <= n;i++)
	{
		for (j = 1;j <= m;j++)
			cout << board[i][j] << " ";
		cout << endl;
	}
	return 0;
}