計算每個島按行和列分隔的島數 · GeeksForGeeks 中文系列教程

# 計算每個島按行和列分隔的島數 > 原文： [https://www.geeksforgeeks.org/count-number-islands-every-island-separated-line/](https://www.geeksforgeeks.org/count-number-islands-every-island-separated-line/) 給定一個只有兩個可能值“ X”和“ O”的矩形矩陣。值“ X”始終以矩形孤島的形式出現，并且這些孤島始終以行和列方式被至少一行“ O”隔開。請注意，島只能沿對角線相鄰。計算給定矩陣中的孤島數量。 **示例**： ``` mat[M][N] = {{'O', 'O', 'O'}, {'X', 'X', 'O'}, {'X', 'X', 'O'}, {'O', 'O', 'X'}, {'O', 'O', 'X'}, {'X', 'X', 'O'} }; Output: Number of islands is 3 mat[M][N] = {{'X', 'O', 'O', 'O', 'O', 'O'}, {'X', 'O', 'X', 'X', 'X', 'X'}, {'O', 'O', 'O', 'O', 'O', 'O'}, {'X', 'X', 'X', 'O', 'X', 'X'}, {'X', 'X', 'X', 'O', 'X', 'X'}, {'O', 'O', 'O', 'O', 'X', 'X'}, }; Output: Number of islands is 4 ``` **我們強烈建議您最小化您的瀏覽器，然后自己嘗試。** 這個想法是計算給定矩陣的所有最左上角。通過檢查以下條件，我們可以檢查“ X”是否位于左上角。 1）如果“ X”位于矩形上方，如果位于其上方的單元格是“ O” 2）如果“ X”位于矩形的最左側，如果位于其左側的單元格是“ O” 請注意，我們必須檢查這兩個條件，因為在一個矩形島中可能有一個以上的頂部單元和一個以上的最左側單元。以下是上述想法的實現。 ## C/C++ ``` // A C++ program to count the number of rectangular // islands where every island is separated by a line #include<iostream> using namespace std; // Size of given matrix is M X N #define M 6 #define N 3 // This function takes a matrix of 'X' and 'O' // and returns the number of rectangular islands // of 'X' where no two islands are row-wise or // column-wise adjacent, the islands may be diagonaly // adjacent int countIslands(int mat[][N]) { ????int count = 0; // Initialize result ????// Traverse the input matrix ????for (int i=0; i<M; i++) ????{ ????????for (int j=0; j<N; j++) ????????{ ????????????// If current cell is 'X', then check ????????????// whether this is top-leftmost of a ????????????// rectangle. If yes, then increment count ????????????if (mat[i][j] == 'X') ????????????{ ????????????????if ((i == 0 || mat[i-1][j] == 'O') && ????????????????????(j == 0 || mat[i][j-1] == 'O')) ????????????????????count++; ????????????} ????????} ????} ????return count; } // Driver program to test above function int main() { ????int mat[M][N] =? {{'O', 'O', 'O'}, ??????????????????????{'X', 'X', 'O'}, ??????????????????????{'X', 'X', 'O'}, ??????????????????????{'O', 'O', 'X'}, ??????????????????????{'O', 'O', 'X'}, ??????????????????????{'X', 'X', 'O'} ????????????????????}; ????cout << "Number of rectangular islands is " ?????????<< countIslands(mat); ????return 0; } ```