title: Rotate Matrix and Delete Characters and Find largest Square
body: <p>A company manufactures walls which can be directly implanted at the site. The company uses small square bricks of material C and material D which have similar looks but have huge difference in quality. The company manufactures walls of square shapes only to optimize their costs.</p>
  <p>A novice employee created a square wall using bricks of material C and D. However, the client had asked the wall to be made of only high-quality material - material C.</p>
  <p>To solve this problem, they will place the wall in a special furnace and heat it such that the material D melts and only material C remains. Material C brick will move down due to gravity if a material D brick below it melts. The new empty space created will be filled by new material C square walls. They also want to use biggest possible C square wall while building the final wall. For this they will position the wall in the furnace in an optimal way i.e. rotate by 90-degrees any number of times, if required, such that the biggest space possible for new material C wall is created. No rotations are possible when the furnace starts heating.</p>
  <p>Given the structure of the original wall created by the novice employee, you need to find out the size of the new C square wall which can be fitted in the final wall which will be delivered to the client.</p>
  <p>Constraints
  1 &lt; N &lt; 100</p>
  <p>Input
  First Line will provide the size of the original wall N.</p>
  <p>Next N lines will provide the type of material (C and D) used for each brick by the novice employee.</p>
  <p>Output
  Size of the biggest possible C square wall which can be fitted in the final wall.</p>
  <p>Time Limit
  1</p>
  <p>Examples
  Example 1</p>
  <p>Input</p>
  <p>4</p>
  <p>C D C D</p>
  <p>C C D C</p>
  <p>D D D D</p>
  <p>C D D D</p>
  <p>Output</p>
  <p>3</p>
  <p>Explanation</p>
  <p>If the wall is placed with its left side at the bottom, space for a new C wall of size 2x2 can be created. This can be visualized as follows</p>
  <p>D C D D</p>
  <p>C D D D</p>
  <p>D C D D</p>
  <p>C C D C</p>
  <p>The melted bricks can be visualized as follows</p>
  <hr />
  <ul>
  <li>C - -</li>
  </ul>
  <p>C C - -</p>
  <p>C C - C</p>
  <p>Hence, the maximum wall size that can be replaced is 2x2.</p>
  <p>If the wall is placed as it is with its original bottom side at the bottom, space for a new C wall of size 3x3 can be created. Post melting, this can be visualized as follows.</p>
  <hr />
  <p>C - - -</p>
  <p>C - - -</p>
  <p>C C C C</p>
  <p>Hence, the maximum wall size that can be replaced is 3x3 in this approach.</p>
  <p>Since no rotations followed by heating is going to a yield a space greater than 3x3, the output is 3.</p>
  <p>Example 2</p>
  <p>Input</p>
  <p>7</p>
  <p>C D D C D D D</p>
  <p>C D D C D D D</p>
  <p>D D D D D D C</p>
  <p>D C D C D D D</p>
  <p>D D D C D C D</p>
  <p>C D D C D C C</p>
  <p>C D C D C C C</p>
  <p>Output</p>
  <p>5</p>
  <p>Explanation</p>
  <p>If the wall is placed with its left side at the bottom, a space for new C wall of size 5x5 can be created. This can be visualized as follows</p>
  <p>D D C D D C C</p>
  <p>D D D D C C C</p>
  <p>D D D D D D C</p>
  <p>C C D C C C D</p>
  <p>D D D D D D C</p>
  <p>D D D C D D D</p>
  <p>C C D D D C C</p>
  <p>When this orientation of the wall is heated, a space for new C wall of size 5x5 is created after the D bricks melt</p>
  <hr />
  <hr />
  <p>_ _ _ _ _ _C</p>
  <p>_ _ _ _ _ C C</p>
  <p>_ _ _ _ _ C C</p>
  <p>C C _ C C C C</p>
  <p>C C C C C C C</p>
  <p>Whereas, if the rotation was not done, the wall formed after the D bricks melt will be as follows</p>
  <hr />
  <hr />
  <p>_ _ _ C _ _ _</p>
  <p>C _ _ C _ _ _</p>
  <p>C _ _ C _ _ C</p>
  <p>C _ _ C _ C C</p>
  <p>C C C C C C C</p>
  <p>When this orientation of the wall is heated, a space for new C wall of size 3x3 only is created after the D bricks melt</p>
  <p>Hence rotation is important and correct answer is 5x5</p>
  <p>Since no rotations followed by heating is going to a yield a space greater than 5x5, the output is 5.</p>
  <pre><code>// matrix rotation by 90 degrees
  void rotate90Clockwise(int a[N][N]) 
  { 
    
      // Traverse each cycle 
      for (int i = 0; i &lt; N / 2; i++) { 
          for (int j = i; j &lt; 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; 
          } 
      } 
  } 
  </code></pre>