C++程式查詢帶有標記星號區域的矩陣

假設我們有一個 n x n 的字元網格，其中包含點 (.) 和星號 (*)。除了兩個單元格外，所有單元格都被標記為點。我們必須標記另外兩個單元格，使它們成為一個矩形的角，矩形的邊平行於座標軸。如果有多種解決方案可用，則返回其中任何一個。

問題類別

在資料結構中，陣列是特定型別元素的有限集合。陣列用於在連續的記憶體位置儲存相同型別的元素。陣列被分配一個特定的名稱，並在各種程式語言中透過該名稱進行引用。要訪問陣列的元素，需要索引。我們使用術語“name[i]”來訪問陣列“name”中位置“i”處的特定元素。各種資料結構，例如棧、佇列、堆、優先佇列，都可以使用陣列實現。陣列上的操作包括插入、刪除、更新、遍歷、搜尋和排序操作。請訪問以下連結以瞭解更多資訊。

https://tutorialspoint.tw/data_structures_algorithms/array_data_structure.htm

因此，如果我們問題的輸入如下所示

那麼輸出將是

步驟

為了解決這個問題，我們將遵循以下步驟 -

n := size of M
x1 := -1, x2 := -1, y1 = -1, y2 = -1
for initialize i := 0, when i < n, update (increase i by 1), do:
   for initialize j := 0, when j < n, update (increase j by 1), do:
      if M[i, j] is same as '*' and x1 is same as -1, then:
         x1 := i, y1 := j
      if M[i, j] is same as '*' and x1 is not equal to -1, then:
         x2 := i, y2 := j
if x1 is same as x2, then:
   if x1 is not equal to n - 1, then:
      M[x1 + 1, y1] = M[x2 + 1, y2] = '*'
   Otherwise
      M[x1 - 1, y1] = M[x2 - 1, y2] = '*'
otherwise when y1 is same as y2, then:
   if y1 is not equal to n - 1, then:
      M[x1, y1 + 1] = M[x2, y2 + 1] = '*'
   Otherwise
      M[x1, y1 - 1] = M[x2, y2 - 1] = '*'
Otherwise
   M[x1, y2] := M[x2, y1] = '*'
for initialize i := 0, when i < n, update (increase i by 1), do:
   for initialize j := 0, when j < n, update (increase j by 1), do:
      print M[i, j]
   move cursor to the next line

示例

讓我們看看下面的實現，以便更好地理解 -

#include <bits/stdc++.h>
using namespace std;
void solve(vector<vector<char>> M){
   int i, j, x1, y1, x2, y2;
   int n = M.size();
   x1 = x2 = y1 = y2 = -1;
   for (i = 0; i < n; i++){
      for (j = 0; j < n; j++){
         if (M[i][j] == '*' && x1 == -1)
            x1 = i, y1 = j;
         if (M[i][j] == '*' && x1 != -1)
            x2 = i, y2 = j;
      }
   }
   if (x1 == x2){
      if (x1 != n - 1)
         M[x1 + 1][y1] = M[x2 + 1][y2] = '*';
      else
         M[x1 - 1][y1] = M[x2 - 1][y2] = '*';
   }
   else if (y1 == y2){
      if (y1 != n - 1)
         M[x1][y1 + 1] = M[x2][y2 + 1] = '*';
      else
         M[x1][y1 - 1] = M[x2][y2 - 1] = '*';
   }
   else
      M[x1][y2] = M[x2][y1] = '*';
   for (i = 0; i < n; i++){
      for (j = 0; j < n; j++)
         printf("%c", M[i][j]);
      printf("\n");
   }
}
int main(){
   vector<vector<char>> matrix = { { '.', '.', '*', '.' }, { '.', '.', '.', '.' },
      { '*', '.', '.', '.' }, { '.', '.', '.', '.' } };
   solve(matrix);
}

輸入

{ { '.', '.', '*', '.' }, { '.', '.', '.', '.' },
   { '*', '.', '.', '.' }, { '.', '.', '.', '.' } }

輸出

*.*.
....
*.*.
....

Arnab Chakraborty

更新於: 2022年4月8日

146 次檢視

開啟您的 職業生涯

完成課程獲得認證

開始學習