给定一个矩阵，其中每个元素都是“O”或“X”，如果被“X”包围，则将“O”替换为“X”。如果“X”位于“O”的正下方、正上方、正左侧和正右侧，则“O”（或一组“O”）被“X”包围。 例如：
null
Input: mat[M][N] = {{'X', 'O', 'X', 'X', 'X', 'X'}, {'X', 'O', 'X', 'X', 'O', 'X'}, {'X', 'X', 'X', 'O', 'O', 'X'}, {'O', 'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'O', 'X', 'O'}, {'O', 'O', 'X', 'O', 'O', 'O'}, };Output: mat[M][N] = {{'X', 'O', 'X', 'X', 'X', 'X'}, {'X', 'O', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'X', 'X', 'X'}, {'O', 'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'O', 'X', 'O'}, {'O', 'O', 'X', 'O', 'O', 'O'}, };
Input: mat[M][N] = {{'X', 'X', 'X', 'X'} {'X', 'O', 'X', 'X'} {'X', 'O', 'O', 'X'} {'X', 'O', 'X', 'X'} {'X', 'X', 'O', 'O'} };
Input: mat[M][N] = {{'X', 'X', 'X', 'X'} {'X', 'X', 'X', 'X'} {'X', 'X', 'X', 'X'} {'X', 'X', 'X', 'X'} {'X', 'X', 'O', 'O'} };
这主要是一个应用程序 洪水填充算法 .这里的主要区别是，如果“O”位于以边界为终点的区域，则它不会被“X”取代。下面是进行这种特殊洪水填充的简单步骤。 1) 遍历给定的矩阵，用一个特殊字符“-”替换所有的“O”。 2) 遍历给定矩阵的四条边并调用 填海（’-‘，O’） 对于边上的每一个“-”。其余的“-”是表示“O”（在原始矩阵中）将被“X”替换的字符。 3) 遍历矩阵，将所有“-”替换为“X”。 让我们用一个例子来看看上述算法的步骤。 下面是输入矩阵。
mat[M][N] = {{'X', 'O', 'X', 'X', 'X', 'X'}, {'X', 'O', 'X', 'X', 'O', 'X'}, {'X', 'X', 'X', 'O', 'O', 'X'}, {'O', 'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'O', 'X', 'O'}, {'O', 'O', 'X', 'O', 'O', 'O'}, };
第一步： 将所有“O”替换为“-”。
mat[M][N] = {{'X', '-', 'X', 'X', 'X', 'X'}, {'X', '-', 'X', 'X', '-', 'X'}, {'X', 'X', 'X', '-', '-', 'X'}, {'-', 'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', '-', 'X', '-'}, {'-', '-', 'X', '-', '-', '-'}, };
第二步： 对值等于“-”的所有边缘元素调用泛光填充（“-”，“O”）
mat[M][N] = {{'X', 'O', 'X', 'X', 'X', 'X'}, {'X', 'O', 'X', 'X', '-', 'X'}, {'X', 'X', 'X', '-', '-', 'X'}, {'O', 'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'O', 'X', 'O'}, {'O', 'O', 'X', 'O', 'O', 'O'}, };
第三步： 将所有“-”替换为“X”。
mat[M][N] = {{'X', 'O', 'X', 'X', 'X', 'X'}, {'X', 'O', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'X', 'X', 'X'}, {'O', 'X', 'X', 'X', 'X', 'X'}, {'X', 'X', 'X', 'O', 'X', 'O'}, {'O', 'O', 'X', 'O', 'O', 'O'}, };
下面是上述算法的实现。
C++
// A C++ program to replace all 'O's with 'X''s if surrounded by 'X' #include<iostream> using namespace std; // Size of given matrix is M X N #define M 6 #define N 6 // A recursive function to replace previous value 'prevV' at '(x, y)' // and all surrounding values of (x, y) with new value 'newV'. void floodFillUtil( char mat[][N], int x, int y, char prevV, char newV) { // Base cases if (x < 0 || x >= M || y < 0 || y >= N) return ; if (mat[x][y] != prevV) return ; // Replace the color at (x, y) mat[x][y] = newV; // Recur for north, east, south and west floodFillUtil(mat, x+1, y, prevV, newV); floodFillUtil(mat, x-1, y, prevV, newV); floodFillUtil(mat, x, y+1, prevV, newV); floodFillUtil(mat, x, y-1, prevV, newV); } // Returns size of maximum size subsquare matrix // surrounded by 'X' int replaceSurrounded( char mat[][N]) { // Step 1: Replace all 'O' with '-' for ( int i=0; i<M; i++) for ( int j=0; j<N; j++) if (mat[i][j] == 'O' ) mat[i][j] = '-' ; // Call floodFill for all '-' lying on edges for ( int i=0; i<M; i++) // Left side if (mat[i][0] == '-' ) floodFillUtil(mat, i, 0, '-' , 'O' ); for ( int i=0; i<M; i++) // Right side if (mat[i][N-1] == '-' ) floodFillUtil(mat, i, N-1, '-' , 'O' ); for ( int i=0; i<N; i++) // Top side if (mat[0][i] == '-' ) floodFillUtil(mat, 0, i, '-' , 'O' ); for ( int i=0; i<N; i++) // Bottom side if (mat[M-1][i] == '-' ) floodFillUtil(mat, M-1, i, '-' , 'O' ); // Step 3: Replace all '-' with 'X' for ( int i=0; i<M; i++) for ( int j=0; j<N; j++) if (mat[i][j] == '-' ) mat[i][j] = 'X' ; } // Driver program to test above function int main() { char mat[][N] = {{ 'X' , 'O' , 'X' , 'O' , 'X' , 'X' }, { 'X' , 'O' , 'X' , 'X' , 'O' , 'X' }, { 'X' , 'X' , 'X' , 'O' , 'X' , 'X' }, { 'O' , 'X' , 'X' , 'X' , 'X' , 'X' }, { 'X' , 'X' , 'X' , 'O' , 'X' , 'O' }, { 'O' , 'O' , 'X' , 'O' , 'O' , 'O' }, }; replaceSurrounded(mat); for ( int i=0; i<M; i++) { for ( int j=0; j<N; j++) cout << mat[i][j] << " " ; cout << endl; } return 0; } |
JAVA
// A Java program to replace // all 'O's with 'X''s if // surrounded by 'X' import java.io.*; class GFG { static int M = 6 ; static int N = 6 ; static void floodFillUtil( char mat[][], int x, int y, char prevV, char newV) { // Base cases if (x < 0 || x >= M || y < 0 || y >= N) return ; if (mat[x][y] != prevV) return ; // Replace the color at (x, y) mat[x][y] = newV; // Recur for north, // east, south and west floodFillUtil(mat, x + 1 , y, prevV, newV); floodFillUtil(mat, x - 1 , y, prevV, newV); floodFillUtil(mat, x, y + 1 , prevV, newV); floodFillUtil(mat, x, y - 1 , prevV, newV); } // Returns size of maximum // size subsquare matrix // surrounded by 'X' static void replaceSurrounded( char mat[][]) { // Step 1: Replace // all 'O' with '-' for ( int i = 0 ; i < M; i++) for ( int j = 0 ; j < N; j++) if (mat[i][j] == 'O' ) mat[i][j] = '-' ; // Call floodFill for // all '-' lying on edges for ( int i = 0 ; i < M; i++) // Left side if (mat[i][ 0 ] == '-' ) floodFillUtil(mat, i, 0 , '-' , 'O' ); for ( int i = 0 ; i < M; i++) // Right side if (mat[i][N - 1 ] == '-' ) floodFillUtil(mat, i, N - 1 , '-' , 'O' ); for ( int i = 0 ; i < N; i++) // Top side if (mat[ 0 ][i] == '-' ) floodFillUtil(mat, 0 , i, '-' , 'O' ); for ( int i = 0 ; i < N; i++) // Bottom side if (mat[M - 1 ][i] == '-' ) floodFillUtil(mat, M - 1 , i, '-' , 'O' ); // Step 3: Replace // all '-' with 'X' for ( int i = 0 ; i < M; i++) for ( int j = 0 ; j < N; j++) if (mat[i][j] == '-' ) mat[i][j] = 'X' ; } // Driver Code public static void main (String[] args) { char [][] mat = {{ 'X' , 'O' , 'X' , 'O' , 'X' , 'X' }, { 'X' , 'O' , 'X' , 'X' , 'O' , 'X' }, { 'X' , 'X' , 'X' , 'O' , 'X' , 'X' }, { 'O' , 'X' , 'X' , 'X' , 'X' , 'X' }, { 'X' , 'X' , 'X' , 'O' , 'X' , 'O' }, { 'O' , 'O' , 'X' , 'O' , 'O' , 'O' }}; replaceSurrounded(mat); for ( int i = 0 ; i < M; i++) { for ( int j = 0 ; j < N; j++) System.out.print(mat[i][j] + " " ); System.out.println( "" ); } } } // This code is contributed // by shiv_bhakt |
Python3
# Python3 program to replace all 'O's with # 'X's if surrounded by 'X' # Size of given matrix is M x N M = 6 N = 6 # A recursive function to replace previous # value 'prevV' at '(x, y)' and all surrounding # values of (x, y) with new value 'newV'. def floodFillUtil(mat, x, y, prevV, newV): # Base Cases if (x < 0 or x > = M or y < 0 or y > = N): return if (mat[x][y] ! = prevV): return # Replace the color at (x, y) mat[x][y] = newV # Recur for north, east, south and west floodFillUtil(mat, x + 1 , y, prevV, newV) floodFillUtil(mat, x - 1 , y, prevV, newV) floodFillUtil(mat, x, y + 1 , prevV, newV) floodFillUtil(mat, x, y - 1 , prevV, newV) # Returns size of maximum size subsquare # matrix surrounded by 'X' def replaceSurrounded(mat): # Step 1: Replace all 'O's with '-' for i in range (M): for j in range (N): if (mat[i][j] = = 'O' ): mat[i][j] = '-' # Call floodFill for all '-' # lying on edges # Left Side for i in range (M): if (mat[i][ 0 ] = = '-' ): floodFillUtil(mat, i, 0 , '-' , 'O' ) # Right side for i in range (M): if (mat[i][N - 1 ] = = '-' ): floodFillUtil(mat, i, N - 1 , '-' , 'O' ) # Top side for i in range (N): if (mat[ 0 ][i] = = '-' ): floodFillUtil(mat, 0 , i, '-' , 'O' ) # Bottom side for i in range (N): if (mat[M - 1 ][i] = = '-' ): floodFillUtil(mat, M - 1 , i, '-' , 'O' ) # Step 3: Replace all '-' with 'X' for i in range (M): for j in range (N): if (mat[i][j] = = '-' ): mat[i][j] = 'X' # Driver code if __name__ = = '__main__' : mat = [ [ 'X' , 'O' , 'X' , 'O' , 'X' , 'X' ], [ 'X' , 'O' , 'X' , 'X' , 'O' , 'X' ], [ 'X' , 'X' , 'X' , 'O' , 'X' , 'X' ], [ 'O' , 'X' , 'X' , 'X' , 'X' , 'X' ], [ 'X' , 'X' , 'X' , 'O' , 'X' , 'O' ], [ 'O' , 'O' , 'X' , 'O' , 'O' , 'O' ] ]; replaceSurrounded(mat) for i in range (M): print ( * mat[i]) # This code is contributed by himanshu77 |
C#
// A C# program to replace // all 'O's with 'X''s if // surrounded by 'X' using System; class GFG { static int M = 6; static int N = 6; static void floodFillUtil( char [,]mat, int x, int y, char prevV, char newV) { // Base cases if (x < 0 || x >= M || y < 0 || y >= N) return ; if (mat[x, y] != prevV) return ; // Replace the color at (x, y) mat[x, y] = newV; // Recur for north, // east, south and west floodFillUtil(mat, x + 1, y, prevV, newV); floodFillUtil(mat, x - 1, y, prevV, newV); floodFillUtil(mat, x, y + 1, prevV, newV); floodFillUtil(mat, x, y - 1, prevV, newV); } // Returns size of maximum // size subsquare matrix // surrounded by 'X' static void replaceSurrounded( char [,]mat) { // Step 1: Replace // all 'O' with '-' for ( int i = 0; i < M; i++) for ( int j = 0; j < N; j++) if (mat[i, j] == 'O' ) mat[i, j] = '-' ; // Call floodFill for // all '-' lying on edges for ( int i = 0; i < M; i++) // Left side if (mat[i, 0] == '-' ) floodFillUtil(mat, i, 0, '-' , 'O' ); for ( int i = 0; i < M; i++) // Right side if (mat[i, N - 1] == '-' ) floodFillUtil(mat, i, N - 1, '-' , 'O' ); for ( int i = 0; i < N; i++) // Top side if (mat[0, i] == '-' ) floodFillUtil(mat, 0, i, '-' , 'O' ); for ( int i = 0; i < N; i++) // Bottom side if (mat[M - 1, i] == '-' ) floodFillUtil(mat, M - 1, i, '-' , 'O' ); // Step 3: Replace // all '-' with 'X' for ( int i = 0; i < M; i++) for ( int j = 0; j < N; j++) if (mat[i, j] == '-' ) mat[i, j] = 'X' ; } // Driver Code public static void Main () { char [,]mat = new char [,] {{ 'X' , 'O' , 'X' , 'O' , 'X' , 'X' }, { 'X' , 'O' , 'X' , 'X' , 'O' , 'X' }, { 'X' , 'X' , 'X' , 'O' , 'X' , 'X' }, { 'O' , 'X' , 'X' , 'X' , 'X' , 'X' }, { 'X' , 'X' , 'X' , 'O' , 'X' , 'O' }, { 'O' , 'O' , 'X' , 'O' , 'O' , 'O' }}; replaceSurrounded(mat); for ( int i = 0; i < M; i++) { for ( int j = 0; j < N; j++) Console.Write(mat[i, j] + " " ); Console.WriteLine( "" ); } } } // This code is contributed // by shiv_bhakt |
PHP
<?php // A PHP program to replace all // 'O's with 'X''s if surrounded by 'X' // Size of given // matrix is M X N $M = 6; $N = 6; // A recursive function to replace // previous value 'prevV' at '(x, y)' // and all surrounding values of // (x, y) with new value 'newV'. function floodFillUtil(& $mat , $x , $y , $prevV , $newV ) { // Base cases if ( $x < 0 || $x >= $GLOBALS [ 'M' ] || $y < 0 || $y >= $GLOBALS [ 'N' ]) return ; if ( $mat [ $x ][ $y ] != $prevV ) return ; // Replace the color at (x, y) $mat [ $x ][ $y ] = $newV ; // Recur for north, // east, south and west floodFillUtil( $mat , $x + 1, $y , $prevV , $newV ); floodFillUtil( $mat , $x - 1, $y , $prevV , $newV ); floodFillUtil( $mat , $x , $y + 1, $prevV , $newV ); floodFillUtil( $mat , $x , $y - 1, $prevV , $newV ); } // Returns size of maximum // size subsquare matrix // surrounded by 'X' function replaceSurrounded(& $mat ) { // Step 1: Replace all 'O' with '-' for ( $i = 0; $i < $GLOBALS [ 'M' ]; $i ++) for ( $j = 0; $j < $GLOBALS [ 'N' ]; $j ++) if ( $mat [ $i ][ $j ] == 'O' ) $mat [ $i ][ $j ] = '-' ; // Call floodFill for all // '-' lying on edges for ( $i = 0; $i < $GLOBALS [ 'M' ]; $i ++) // Left side if ( $mat [ $i ][0] == '-' ) floodFillUtil( $mat , $i , 0, '-' , 'O' ); for ( $i = 0; $i < $GLOBALS [ 'M' ]; $i ++) // Right side if ( $mat [ $i ][ $GLOBALS [ 'N' ] - 1] == '-' ) floodFillUtil( $mat , $i , $GLOBALS [ 'N' ] - 1, '-' , 'O' ); for ( $i = 0; $i < $GLOBALS [ 'N' ]; $i ++) // Top side if ( $mat [0][ $i ] == '-' ) floodFillUtil( $mat , 0, $i , '-' , 'O' ); for ( $i = 0; $i < $GLOBALS [ 'N' ]; $i ++) // Bottom side if ( $mat [ $GLOBALS [ 'M' ] - 1][ $i ] == '-' ) floodFillUtil( $mat , $GLOBALS [ 'M' ] - 1, $i , '-' , 'O' ); // Step 3: Replace all '-' with 'X' for ( $i = 0; $i < $GLOBALS [ 'M' ]; $i ++) for ( $j = 0; $j < $GLOBALS [ 'N' ]; $j ++) if ( $mat [ $i ][ $j ] == '-' ) $mat [ $i ][ $j ] = 'X' ; } // Driver Code $mat = array ( array ( 'X' , 'O' , 'X' , 'O' , 'X' , 'X' ), array ( 'X' , 'O' , 'X' , 'X' , 'O' , 'X' ), array ( 'X' , 'X' , 'X' , 'O' , 'X' , 'X' ), array ( 'O' , 'X' , 'X' , 'X' , 'X' , 'X' ), array ( 'X' , 'X' , 'X' , 'O' , 'X' , 'O' ), array ( 'O' , 'O' , 'X' , 'O' , 'O' , 'O' )); replaceSurrounded( $mat ); for ( $i = 0; $i < $GLOBALS [ 'M' ]; $i ++) { for ( $j = 0; $j < $GLOBALS [ 'N' ]; $j ++) echo $mat [ $i ][ $j ]. " " ; echo "" ; } // This code is contributed by ChitraNayal ?> |
Javascript
<script> // A Javascript program to replace // all 'O's with 'X''s if // surrounded by 'X' let M = 6; let N = 6; function floodFillUtil(mat,x,y,prevV,newV) { // Base cases if (x < 0 || x >= M || y < 0 || y >= N) return ; if (mat[x][y] != prevV) return ; // Replace the color at (x, y) mat[x][y] = newV; // Recur for north, // east, south and west floodFillUtil(mat, x + 1, y, prevV, newV); floodFillUtil(mat, x - 1, y, prevV, newV); floodFillUtil(mat, x, y + 1, prevV, newV); floodFillUtil(mat, x, y - 1, prevV, newV); } // Returns size of maximum // size subsquare matrix // surrounded by 'X' function replaceSurrounded(mat) { // Step 1: Replace // all 'O' with '-' for (let i = 0; i < M; i++) for (let j = 0; j < N; j++) if (mat[i][j] == 'O ') mat[i][j] = ' - '; // Call floodFill for // all ' - ' lying on edges for (let i = 0; i < M; i++) // Left side if (mat[i][0] == ' - ') floodFillUtil(mat, i, 0, ' - ', ' O '); for (let i = 0; i < M; i++) // Right side if (mat[i][N - 1] == ' - ') floodFillUtil(mat, i, N - 1, ' - ', ' O '); for (let i = 0; i < N; i++) // Top side if (mat[0][i] == ' - ') floodFillUtil(mat, 0, i, ' - ', ' O '); for (let i = 0; i < N; i++) // Bottom side if (mat[M - 1][i] == ' - ') floodFillUtil(mat, M - 1, i, ' - ', ' O '); // Step 3: Replace // all ' - ' with ' X ' for (let i = 0; i < M; i++) for (let j = 0; j < N; j++) if (mat[i][j] == ' - ') mat[i][j] = ' X '; } // Driver Code let mat = [ [ ' X ', ' O ', ' X ', ' O ', ' X ', ' X ' ], [ ' X ', ' O ', ' X ', ' X ', ' O ', ' X ' ], [ ' X ', ' X ', ' X ', ' O ', ' X ', ' X ' ], [ ' O ', ' X ', ' X ', ' X ', ' X ', ' X ' ], [ ' X ', ' X ', ' X ', ' O ', ' X ', ' O ' ], [ ' O ', ' O ', ' X ', ' O ', ' O ', ' O' ] ]; replaceSurrounded(mat); for (let i = 0; i < M; i++) { for (let j = 0; j < N; j++) document.write(mat[i][j] + " " ); document.write( "<br>" ); } // This code is contributed by rag2127 </script> |
输出：
X O X O X X X O X X X X X X X X X X O X X X X X X X X O X O O O X O O O
上述解的时间复杂度为O（MN）。请注意，矩阵的每个元素最多处理三次。 本文由 安诺尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
