Pertanyaan untuk mengemas kini bilangan sel bukan kosong yang disambungkan dalam matriks

Matriks boleh dianggap sebagai koleksi sel yang disusun dalam baris dan lajur. Setiap sel boleh mengandungi nilai, yang boleh kosong atau tidak kosong. Dalam pengaturcaraan komputer, matriks sering digunakan untuk mewakili data dalam grid dua dimensi.

Dalam artikel ini, kami akan membincangkan cara mengira bilangan sel tidak kosong yang bersambung dalam matriks dengan cekap, dengan mengambil kira kemungkinan kemas kini pada matriks. Kami akan meneroka cara yang berbeza untuk menyelesaikan masalah ini dan menyediakan contoh kod dunia sebenar untuk menunjukkan pelaksanaan.

Tatabahasa

Sintaks asas untuk menanyakan bilangan sel bukan kosong yang bersambung dalam matriks dan mengemas kininya menggunakan C/C++ boleh ditakrifkan seperti berikut -

int queryCount(int matrix[][MAX_COLS], int rows, int cols);

Di mana matriks ialah input "matriks", "baris" dan "kol" masing-masing mewakili bilangan baris dan lajur dalam matriks. Fungsi "queryCount" mengembalikan nilai integer yang mewakili bilangan sel bukan kosong yang disambungkan dalam matriks.

Algoritma

Untuk menyelesaikan masalah ini, kita boleh mengikuti algoritma berikut -

Langkah 1 - Mulakan pembolehubah "kiraan" kepada 0, ini akan menyimpan kiraan sel bukan kosong yang bersambung.

Langkah 2 - Ulangi setiap sel dalam matriks.

Langkah 3 - Untuk setiap sel, semak sama ada ia tidak kosong (iaitu mengandungi nilai bukan nol).

Langkah 4 - Jika sel tidak kosong, tambahkan Kiraan sebanyak 1.

Langkah 5 - Periksa sama ada sel mempunyai sel bersebelahan yang tidak kosong.

Langkah 6 - Jika sel bersebelahan tidak kosong, tambahkan "kiraan" sebanyak 1.

Langkah 7 - Ulang langkah 5-6 untuk semua sel bersebelahan.

Langkah 8 - 8: Selepas melelaran melalui semua sel dalam matriks, kembalikan "kiraan" sebagai hasil akhir.

Kaedah

• Kaedah 1 - Cara biasa untuk menyelesaikan masalah ini ialah menggunakan algoritma Depth First Search (DFS)

• Kaedah 2 - Satu lagi cara untuk melaksanakan pertanyaan untuk mencari kiraan sel tidak kosong dengan cantuman dalam matriks yang dikemas kini ialah menggunakan algoritma Breadth-First Search (BFS).

Kaedah 1

Dalam pendekatan ini, algoritma DFS melibatkan merentasi matriks secara rekursif dan menjejaki sel yang dilawati untuk mengelakkan pengiraan dua kali.

Contoh 1

Kaedah ini melakukan carian mendalam-pertama pada matriks dua dimensi. Dimensi, nilai sel dan bilangan pertanyaan matriks ditentukan secara rawak. Subrutin countConnectedCells melaksanakan DFS dan mengembalikan kiraan sel bukan nol yang bersambung, bermula dengan sel pada baris dan lajur yang ditentukan. Fungsi updateCell mengemas kini nilai sel dalam matriks. Fungsi utama memulakan benih rawak menggunakan masa semasa, kemudian menjana saiz dan elemen matriks rawak, diikuti dengan bilangan pertanyaan rawak. Untuk setiap pertanyaan, kod secara rawak memilih pertanyaan kiraan (1) atau pertanyaan kemas kini (2) dan melakukan tindakan yang sesuai. Jika jenis pertanyaan ialah 1, fungsi countConnectedCells dipanggil untuk menentukan kiraan sel yang bersambung, tidak kosong dan mencetak hasilnya. Jika jenis pertanyaan ialah 2, panggil fungsi updateCell untuk melaraskan nilai sel yang ditentukan.

#include <iostream>
using namespace std;

const int MAX_SIZE = 100; // Maximum size of the matrix

// Function to count connected non-empty cells using DFS
int countConnectedCells(int matrix[][MAX_SIZE], int rows, int cols, int row, int col, int visited[][MAX_SIZE]) {
   if (row < 0 || row >= rows || col < 0 || col >= cols || matrix[row][col] == 0 || visited[row][col])
      return 0;

   visited[row][col] = 1;
   int count = 1; // Counting the current cell as non-empty
   count += countConnectedCells(matrix, rows, cols, row - 1, col, visited); // Check top cell
   count += countConnectedCells(matrix, rows, cols, row + 1, col, visited); // Check bottom cell
   count += countConnectedCells(matrix, rows, cols, row, col - 1, visited); // Check left cell
   count += countConnectedCells(matrix, rows, cols, row, col + 1, visited); // Check right cell

   return count;
}

// Function to update a cell in the matrix
void updateCell(int matrix[][MAX_SIZE], int rows, int cols, int row, int col, int newValue) {
   matrix[row][col] = newValue;
}

// Function to initialize the matrix
void initializeMatrix(int matrix[][MAX_SIZE], int rows, int cols) {
   for (int i = 0; i <rows; i++) {
      for (int j = 0; j < cols; j++) {
         cin >> matrix[i][j]; // Taking input for each cell in the matrix
      }
   }
}

int main() {
   int rows, cols; // Input matrix size
   cin >> rows >> cols; // Taking input for matrix size

   int matrix[MAX_SIZE][MAX_SIZE]; // Matrix to store the values
   int visited[MAX_SIZE][MAX_SIZE] = {0}; // Visited matrix to keep track of visited cells

   initializeMatrix(matrix, rows, cols); // Initialize the matrix with input values

   int queries; // Input number of queries
   cin >> queries; // Taking input for number of queries

   for (int i = 0; i < queries; i++) {
      int queryType; // Input query type (1 for count query, 2 for update query)
      cin >> queryType; // Taking input for query type

      if (queryType == 1) {
         int row, col; // Input row and column for count query
         cin >> row >> col; // Taking input for row and column
         int count = countConnectedCells(matrix, rows, cols, row, col, visited); // Call countConnectedCells function
         cout << "Count of connected non-empty cells at (" << row << ", " << col << "): " << count << endl; // Print result
      } else if (queryType == 2) {
         int row, col, newValue; // Input row, column, and new value for update query
         cin >> row >> col >> newValue; // Taking input for row, column, and new value
         updateCell(matrix, rows, cols, row, col, newValue); // Call updateCell function
      }
   }
   return 0;
}

Output

Count of connected non-empty cells at (1, 2): 0
Count of connected non-empty cells at (0, 1): 2

Kaedah 2

Dalam pendekatan ini, Breadth First Search (BFS) ialah satu lagi algoritma traversal graf yang boleh digunakan untuk mencari bilangan sel bukan kosong yang disambungkan dalam matriks. Dalam BFS, kita bermula dari sel tertentu dan meneroka semua sel jirannya dengan cara yang luas-pertama (iaitu, lapisan demi lapisan). Kami menggunakan baris gilir untuk menjejaki sel yang sedang diakses dan menandakan sel yang telah diakses untuk mengelakkan berbilang kiraan.

Contoh 2

Kod ini membentuk perisian yang melaksanakan algoritma carian luas pertama pada matriks dua dimensi. Dimensi matriks, nilai sel dan bilangan pertanyaan dijana secara sewenang-wenangnya. Kod ini mengandungi dua subrutin: satu untuk melaksanakan BFS dan satu lagi untuk melaraskan sel dalam matriks.

Operasi BFS bermula dengan sel yang dipilih secara rawak dan menyemak sel jirannya untuk menentukan sama ada ia saling bersambung dan tidak berpenghuni. Jika ya, mereka akan ditambahkan pada baris gilir dan diproses dengan cara yang sama. Mengemas kini sel dalam matriks hanya melibatkan perubahan nilainya. Selepas menjana nombor matriks dan pertanyaan, kod secara rawak memilih pertanyaan BFS atau pertanyaan kemas kini dan melaksanakan operasi yang sesuai. Hasil pertanyaan BFS ialah kiraan sel tidak berpenghuni yang saling berkaitan bermula dari sel yang dipilih.

Kod

#include <iostream>
#include <queue>
#include <ctime>
#include <cstdlib>

using namespace std;

const int MAX_SIZE = 100;

// Function to perform Breadth-First Search (BFS)
int bfs(int matrix[][MAX_SIZE], int rows, int cols, int row, int col, int visited[][MAX_SIZE]) {
   int count = 0;
   queue<pair<int, int>> q;
   q.push({row, col});

   while (!q.empty()) {
      pair<int, int> currentCell = q.front();
      q.pop();

      int currentRow = currentCell.first;
      int currentCol = currentCell.second;

      if (currentRow >= 0 && currentRow <rows && currentCol >= 0 && currentCol < cols && !visited[currentRow][currentCol] && matrix[currentRow][currentCol] == 1) {
         count++;
         visited[currentRow][currentCol] = 1;

         q.push({currentRow - 1, currentCol});
         q.push({currentRow + 1, currentCol});
         q.push({currentRow, currentCol - 1});
         q.push({currentRow, currentCol + 1});
      }
   }
   return count;
}
// Function to update a cell in the matrix
void updateCell(int matrix[][MAX_SIZE], int row, int col, int newValue) {
   matrix[row][col] = newValue;
}

// Function to generate a random integer between min and max (inclusive)
int randomInt(int min, int max) {
   return rand() % (max - min + 1) + min;
}

int main() {
   srand(time(0));

   int rows = randomInt(1, 10);
   int cols = randomInt(1, 10);

   int matrix[MAX_SIZE][MAX_SIZE];
   int visited[MAX_SIZE][MAX_SIZE] = {0};

   for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
         matrix[i][j] = randomInt(0, 1);
      }
   }

   int queries = randomInt(1, 5);

   for (int i = 0; i < queries; i++) {
      int queryType = randomInt(1, 2);

      if (queryType == 1) {
         int row = randomInt(0, rows - 1);
         int col = randomInt(0, cols - 1);
         int count = bfs(matrix, rows, cols, row, col, visited);
         cout << "Count of connected non-empty cells at (" << row << ", " << col << "): " << count << endl;
      } else if (queryType == 2) {
         int row = randomInt(0, rows - 1);
         int col = randomInt(0, cols - 1);
         int newValue = randomInt(0, 1);
         updateCell(matrix, row, col, newValue);
      }
   }
   return 0;
}

Output

Count of connected non-empty cells at (0, 0): 0

Kesimpulan

Dalam artikel ini, kami membincangkan dua kaedah untuk mencari bilangan sel bukan kosong yang disambungkan dalam matriks dan mengemas kininya menggunakan C/C++. Algoritma Depth First Search (DFS) dan carian kesatuan (penyatuan set bercapah). Adalah penting untuk menganalisis kerumitan masa dan kerumitan ruang bagi setiap kaedah sebelum memilih kaedah yang paling sesuai untuk kes penggunaan tertentu.

Atas ialah kandungan terperinci Pertanyaan untuk mengemas kini bilangan sel bukan kosong yang disambungkan dalam matriks. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!