LeetCode surrounded region-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode surrounded region。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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: Notice that an ‘O’ should not be flipped if:

It is on the border, or
It is adjacent to an ‘O’ that should not be flipped.
The bottom ‘O’ is on the border, so it is not flipped.
The other three ‘O’ form a surrounded region, so they are flipped.

思路：考虑到目标是“把所有内部被X围住的O转成X”，把所有外围（还有与外围相连的）的O 转成 F （也可以是其他别的字符）；
然后，遍历整个矩阵，把此时所有O转成X，把所有F恢复成O.文章来源地址https://www.toymoban.com/news/detail-467380.html

public void solve(char[][] ma)
    {
        int n = ma.length;
        int m = ma[0].length;
        for(int i=0;i<n;i++)
        {
           if(ma[i][0]=='O')
           {
               free(ma,i,0);
           }

           if(ma[i][m-1]=='O')
           {
               free(ma,i,m-1);
           }
        }

        for(int j=1;j<m-1;j++)
        {
            if(ma[0][j]=='O')
            {
                free(ma,0,j);
            }
            if(ma[n-1][j]=='O')
            {
                free(ma,n-1,j);
            }
        }

        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(ma[i][j]=='O')
                {
                    ma[i][j]='X';
                }
                  if(ma[i][j]=='F')
                {
                    ma[i][j]='O';
                }
            }
        }
    }
    public void free(char[][] ma, int i, int j)
    {
        if(i<0||i>=ma.length||j<0||j>=ma[0].length||ma[i][j]!='O')
        {
            return;
        }
        ma[i][j]='F';
        free(ma,i-1,j);
        free(ma,i,j-1);
        free(ma,i+1,j);
        free(ma,i,j+1);
    }