C++程序查找带有标记星号区域的矩阵

假设我们有一个 n x n 的字符网格，其中包含点 (.) 和星号 (*)。除了两个单元格外，所有单元格都被标记为点。我们必须标记另外两个单元格，使它们成为一个矩形的角，矩形的边平行于坐标轴。如果有多种解决方案可用，则返回其中任何一个。

问题类别

在数据结构中，数组是特定类型元素的有限集合。数组用于在连续的内存位置存储相同类型的元素。数组被分配一个特定的名称，并在各种编程语言中通过该名称进行引用。要访问数组的元素，需要索引。我们使用术语“name[i]”来访问数组“name”中位置“i”处的特定元素。各种数据结构，例如栈、队列、堆、优先队列，都可以使用数组实现。数组上的操作包括插入、删除、更新、遍历、搜索和排序操作。请访问以下链接以了解更多信息。

https://tutorialspoint.com/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 次查看

开启您的 职业生涯

完成课程获得认证

开始学习