Count Total Number of Colored Cells

Problem Statement

In this problem, we are working with an infinitely large two-dimensional grid made up of unit cells. Initially, all cells are uncolored. Over a series of n minutes, a coloring process takes place. Here’s how it works:

1. In the first minute, we start by coloring any chosen cell blue.
2. For every subsequent minute, each uncolored cell that is adjacent (touches at least one side) to a blue cell is also colored blue.

The goal is to determine the total number of blue colored cells on the grid after n minutes.

Examples

Example 1

Input:

n = 1

Output:

1

Explanation:

After 1 minute, there is only 1 blue cell, so we return 1.

Example 2

Input:

n = 2

Output:

5

Explanation:

After 2 minutes, there are 4 colored cells on the boundary and 1 in the center, so we return 5.

Constraints

• 1 <= n <= 105

Approach and Intuition

Given the problem's unique way of coloring cells across minutes, we can derive the pattern of cell expansion:

1. In the first minute, we start with one blue cell.
2. Every minute thereafter, the squared area of colored cells grows, primarily due to the cells touching the sides of the already colored area. Specifically, for each subsequent minute:
   • Each side of the current square of blue cells "expands" outward, adding a layer of newly colored cells that surrounds the existing blue region.

Given a cell selected randomly at the beginning, the growth of the colored area can be visualized as follows:

• Minute 1: A single cell is colored.
• Minute 2: Additional cells surrounding the initial cell are colored, resulting in a total of 5 cells - forming a plus shape.
• Minute 3 and beyond: This pattern continues, where each minute adds a layer around the existing blue cells, expanding the blue region in a square shape with increasingly larger perimeters.

Calculation:

The number of blue cells can thus be calculated using the growth pattern:

• Basically, the area grows in a diamond (or square when rotated) pattern. The maximum distance from the initially colored cell to any cell in the boundary of the square formed by the end of n minutes is n - 1 cells away in the cardinal directions.
• The cells formed by this growth in n minutes is 2n^2 - 2n + 1. This formula comes from observing that the expansion forms concentric diamonds of increasing size, where each side of the diamond i layers away from the center is 2i cells plus the center cell.

Understanding these points helps in visualizing and solving the problem efficiently without the need for simulating the process on an actual grid, thus optimizing for larger values of n within computational constraints.

Solutions

class Solution {
public:
    long long countColoredCells(int m) { return 1 + (long long)m * (m - 1) * 2; }
};