旋转矩阵并删除字符并找到最大的正方形

Question

一家公司生产可直接植入现场的墙壁。公司使用的是materialC和materialD的小方砖，外观相似，但质量差别很大。该公司制造方形墙只是为了优化成本。

新手用 material C 和 D 的砖砌了一面方墙。但是，客户要求只用优质 material - material C.

为了解决这个问题，他们将把墙放在一个特殊的炉子里加热，这样 material D 就会熔化，只剩下 material C。 Material 如果下面的 material D 砖熔化，C 砖将由于重力向下移动。创建的新空 space 将由新的 material C 方形墙填充。他们还想在建造最后一面墙时使用尽可能大的 C 方形墙。为此，他们将以最佳方式将墙放置在炉子中，即如果需要，可以任意次数地旋转 90 度，以便创建最大的 space 新 material C 墙。炉子开始加热时不能旋转。

鉴于新手创建的原始墙的结构，您需要找出新的 C 方墙的尺寸，该尺寸可以安装在将交付给客户的最终墙中。

约束条件 1 < N < 100

输入第一行会提供原墙的尺寸N.

接下来的 N 行将提供新手员工用于每块砖的 material（C 和 D）的类型。

输出可安装在最终墙中的最大可能的 C 方形墙的尺寸。

时间限制 1

例子示例 1

输入

4

C D C D

C C D C

D D D D

C D D D

输出

3

说明

如果墙的左侧在底部放置，space 可以创建大小为 2x2 的新 C 墙。这可以可视化如下

D C D D

C D D D

D C D D

C C D C

熔化的砖块可视化如下

C - -

C C - -

C C - C

因此，可以更换的最大墙尺寸为 2x2。

如果墙按原样放置，其原始底面在底部，space 可以创建大小为 3x3 的新 C 墙。 Post 熔化，这可以形象化如下。

C - - -

C C C C

因此，在这种方法中，可以更换的最大墙尺寸为 3x3。

因为没有旋转后加热会产生大于 3x3 的 space，输出为 3。

示例 2

输入

7

C D D C D D D

D D D D D D C

D C D C D D D

D D D C D C D

C D D C D C C

C D C D C C C

输出

5

说明

如果墙的左侧位于底部，则可以创建一个 space 大小为 5x5 的新 C 墙。这可以可视化如下

D D C D D C C

D D D D C C C

D D D D D D C

C C D C C C D

D D D D D D C

D D D C D D D

C C D D D C C

当墙的这个方向被加热时，在 D 砖熔化后 space 会创建一个尺寸为 5x5 的新 C 墙

_ _ _ _ _ _C

_ _ _ _ _ C C

C C _ C C C C

C C C C C C C

而如果不进行旋转，D砖熔化后形成的墙体如下

_ _ _ C _ _ _

C _ _ C _ _ _

C _ _ C _ _ C

C _ _ C _ C C

C C C C C C C

当墙的这个方向被加热时，space 尺寸为 3x3 的新 C 墙仅在 D 砖熔化后创建

因此旋转很重要，正确答案是 5x5

因为没有旋转后加热会产生大于 5x5 的 space，输出为 5。

// matrix rotation by 90 degrees
void rotate90Clockwise(int a[N][N]) 
{ 
  
    // Traverse each cycle 
    for (int i = 0; i < N / 2; i++) { 
        for (int j = i; j < N - i - 1; j++) { 
  
            // Swap elements of each cycle 
            // in clockwise direction 
            int temp = a[i][j]; 
            a[i][j] = a[N - 1 - j][i]; 
            a[N - 1 - j][i] = a[N - 1 - i][N - 1 - j]; 
            a[N - 1 - i][N - 1 - j] = a[j][N - 1 - i]; 
            a[j][N - 1 - i] = temp; 
        } 
    } 
}

Answer 1

我不确切知道你把墙放在什么数据结构中，但假设它是：

std::vector<std::vector<char>> wall;

为了能够使用 std::sort 执行熔化，最好在外部向量中有列，在内部向量中有行。

// melting bricks
for (int col = 0; col < wall.size(); ++col) //column of bricks
{
    for (int row = 0; row < wall[0].size(); ++row) //row of bricks
    {
        if (wall[col][row] == 'D') wall[col][row] = 0;
    }
}

// applying gravity i.e. sorting
for (int col = 0; col < wall.size(); ++col) //column of bricks
{
    std::sort(wall[column].begin(), wall[column].end());
}

我还没有对此进行测试，因此您可能需要进行调试。

要找到适合的最大正方形，一种方法是旋转墙壁并在每次旋转时熔化，然后搜索最大正方形，或许可以使用 while 循环。

此外，将您的代码组织成类也很重要，例如墙壁、火炉等

旋转矩阵并删除字符并找到最大的正方形

Rotate Matrix and Delete Characters and Find largest Square

c++

arrays

algorithm

logic

matrix