Beats 0 %
Intuition\nThe goal of the problem is to contain a viral outbreak on a grid by building walls around the most threatening regions. The algorithm needs to identi
### Intuition\nThe goal of the problem is to contain a viral outbreak on a grid by building walls around the most threatening regions. The algorithm needs to identify these regions, calculate how many walls are required to contain them, and then process the spread of the infection accordingly.\n\n### Approach\n1. **Identifying Regions**: We iterate over the grid to find all infected blocks (denoted by `1`). For each infected block, we perform a depth-first search (DFS) to count its size and potential spread.\n  \n2. **Selecting the Most Threatening Block**: After identifying all infected blocks, we determine which block poses the greatest threat based on its potential spread.\n\n3. **Building Walls**: For the most threatening block, we calculate how many walls are required to contain it. We then mark that block as contained.\n\n4. **Contamination Spread**: After building the walls, we mark adjacent empty cells to potentially become infected in the next iteration and update the grid.\n\n5. **Repeating the Process**: We repeat the above steps until there are no more infected blocks.\n\n### Complexity\n- **Time Complexity**: The time complexity is approximately \\(O(m \\times n)\\) in the worst case, where \\(m\\) is the number of rows and \\(n\\) is the number of columns. This is due to the multiple passes over the grid for DFS and processing.\n\n- **Space Complexity**: The space complexity is \\(O(m \\times n)\\) due to the additional data structures used (like the visited grid and temporary infection markings).\n\n### Code Breakdown\n\n```cpp\nclass Solution {\npublic:\n    // Main function to contain the virus\n    int containVirus(vector<vector<int>>& inf) {\n        int m = inf.size(); // Number of rows in the grid\n        int n = inf[0].size(); // Number of columns in the grid\n        int ans = FindWalls(m, n, inf); // Call the function to find and build walls\n        return ans; // Return the total number of walls built\n    }\n```\n- **`containVirus`**: Initializes grid dimensions and calls `FindWalls`.\n\n---\n\n```cpp\n    // Function to find and build walls around the most threatening infection region\n    int FindWalls(int m, int n, vector<vector<int>>& inf) {\n        int ans = 0; // Total walls built\n        int maxima = 0; // Maximum potential spread from a block\n        int start_x = 0; // X coordinate of the block to process\n        int start_y = 0; // Y coordinate of the block to process\n\n        while (true) { // Continue until there are no infected regions\n            maxima = 0; // Reset maximum for this iteration\n            int local_ans = 0; // Walls needed for the current block\n            vector<vector<int>> v(m, vector<int>(n, 0)); // Visited grid for DFS\n\n            // Iterate through the grid to find all infected blocks\n            for (int i = 0; i < m; i++) {\n                for (int j = 0; j < n; j++) {\n                    // If the cell is infected and not visited\n                    if (inf[i][j] == 1 && v[i][j] == 0) {\n                        initialize(v, m, n, inf); // Initialize visited grid\n                        local_ans = blocks(i, j, v, inf, m, n); // Count the size of the block\n                        if (local_ans > maxima) {\n                            start_x = i; // Update coordinates of the largest block\n                            start_y = j;\n                        }\n                        maxima = max(maxima, local_ans); // Update maximum spread\n                    }\n                }\n            }\n\n            // If no infected block is found, exit the loop\n            if (maxima == 0) return ans;\n\n            // Reset visited grid for the next block\n            for (int i = 0; i < m; i++)\n                for (int j = 0; j < n; j++)\n                    v[i][j] = 0;\n\n            // Count the walls needed to contain the largest spread block\n            ans += blockToSpread(start_x, start_y, v, inf, m, n);\n            vector<vector<int>> G(m, vector<int>(n, 0)); // Grid to track dismantling\n            Dismantle(start_x, start_y, inf, G, m, n); // Dismantle the infected block\n            ContaminateMarking(inf, m, n); // Mark adjacent cells for contamination\n            Contaminate(inf, m, n); // Update grid after contamination\n        }\n    }\n```\n- **`FindWalls`**: This function identifies infected regions and decides where to build walls.\n\n  - **Inner Loop**: Iterates over the grid to find infected blocks.\n  - **DFS (`blocks`)**: Used to count the size of each infected block.\n  - **Wall Counting**: Calculates the number of walls needed for the most threatening block.\n  - **Contamination Management**: Calls functions to dismantle infected areas and mark surrounding cells for contamination.\n\n---\n\n```cpp\n    // Initialize the visited grid\n    void initialize(vector<vector<int>>& v, int m, int n, vector<vector<int>>& inf) {\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                // Mark non-infected cells as unvisited\n                if (inf[i][j] == 0)\n                    v[i][j] = 0;\n            }\n        }\n    }\n```\n- **`initialize`**: Resets the visited grid to track which cells have been processed.\n\n---\n\n```cpp\n    // DFS to count the size of the infected block starting from (x, y)\n    int blocks(int x, int y, vector<vector<int>>& v, vector<vector<int>>& inf, int m, int n) {\n        // Out of bounds check\n        if (x < 0 || x >= m || y < 0 || y >= n)\n            return 0;\n\n        // If already visited, return\n        if (v[x][y] == 1)\n            return 0;\n\n        v[x][y] = 1; // Mark the cell as visited\n\n        // If the cell is empty, count it as a potential spread\n        if (inf[x][y] == 0)\n            return 1;\n        // If the cell has a wall, it can\'t be counted\n        if (inf[x][y] == -1)\n            return 0;\n\n        int sum = 0; // To count the size of the block\n        // If the cell is infected, continue DFS to adjacent cells\n        if (inf[x][y] == 1) {\n            sum += blocks(x + 1, y, v, inf, m, n);\n            sum += blocks(x - 1, y, v, inf, m, n);\n            sum += blocks(x, y - 1, v, inf, m, n);\n            sum += blocks(x, y + 1, v, inf, m, n);\n        }\n        return sum; // Return the total count\n    }\n```\n- **`blocks`**: Performs a depth-first search to count the number of infected cells in a block.\n\n---\n\n```cpp\n    // Count potential spread from a block starting at (x, y)\n    int blockToSpread(int x, int y, vector<vector<int>>& v, vector<vector<int>>& inf, int m, int n) {\n        // Out of bounds check\n        if (x < 0 || x >= m || y < 0 || y >= n)\n            return 0;\n\n        // If the cell is empty, count it as potential spread\n        if (inf[x][y] == 0) {\n            return 1;\n        }\n\n        // If already visited, return\n        if (v[x][y] == 1)\n            return 0;\n\n        v[x][y] = 1; // Mark the cell as visited\n\n        int sum = 0; // To count potential spread\n        // If the cell is infected, continue to adjacent cells\n        if (inf[x][y] == 1) {\n            sum += blockToSpread(x + 1, y, v, inf, m, n);\n            sum += blockToSpread(x - 1, y, v, inf, m, n);\n            sum += blockToSpread(x, y - 1, v, inf, m, n);\n            sum += blockToSpread(x, y + 1, v, inf, m, n);\n        }\n        return sum; // Return the total count\n    }\n```\n- **`blockToSpread`**: Similar to `blocks`, but focuses on counting how many adjacent empty cells can potentially become infected.\n\n---\n\n```cpp\n    // Dismantle the infected block by marking it with walls\n    void Dismantle(int x, int y, vector<vector<int>>& inf, vector<vector<int>>& G, int m, int n) {\n        // Out of bounds check\n        if (x < 0 || x >= m || y < 0 || y >= n)\n            return;\n\n        // If already processed, return\n        if (G[x][y] == 1)\n            return;\n\n        G[x][y] = 1; // Mark this cell as processed\n\n        // If the cell is infected, mark it as a wall\n        if (inf[x][y] == 1\n\n) {\n            inf[x][y] = -1; // Mark as wall\n            // Recursively dismantle adjacent cells\n            Dismantle(x + 1, y, inf, G, m, n);\n            Dismantle(x - 1, y, inf, G, m, n);\n            Dismantle(x, y + 1, inf, G, m, n);\n            Dismantle(x, y - 1, inf, G, m, n);\n        } else {\n            return; // Return if it\'s not infected\n        }\n    }\n```\n- **`Dismantle`**: Marks infected cells as walls (`-1`), effectively containing the region.\n\n---\n\n```cpp\n    // Mark adjacent cells of infected blocks for contamination\n    void ContaminateMarking(vector<vector<int>>& inf, int m, int n) {\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                // If the cell is infected, mark its empty neighbors\n                if (inf[i][j] == 1) {\n                    ContaminateBlockMarking(i + 1, j, inf, m, n);\n                    ContaminateBlockMarking(i - 1, j, inf, m, n);\n                    ContaminateBlockMarking(i, j + 1, inf, m, n);\n                    ContaminateBlockMarking(i, j - 1, inf, m, n);\n                }\n            }\n        }\n        return; // End of function\n    }\n```\n- **`ContaminateMarking`**: Marks adjacent empty cells to indicate they can become infected in the next iteration.\n\n---\n\n```cpp\n    // Mark an adjacent empty cell as temporarily infected\n    void ContaminateBlockMarking(int x, int y, vector<vector<int>>& inf, int m, int n) {\n        // Out of bounds check\n        if (x < 0 || x >= m || y < 0 || y >= n)\n            return;\n\n        // If the cell is empty, mark it as temporarily infected\n        if (inf[x][y] == 0)\n            inf[x][y] = -2;\n\n        return; // End of function\n    }\n```\n- **`ContaminateBlockMarking`**: Marks an empty cell as temporarily infected (`-2`).\n\n---\n\n```cpp\n    // Convert temporarily infected cells back to infected\n    void Contaminate(vector<vector<int>>& inf, int m, int n) {\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                // If a cell is temporarily infected, convert it to infected\n                if (inf[i][j] == -2)\n                    inf[i][j] = 1;\n            }\n        }\n        return; // End of function\n    }\n};\n```\n- **`Contaminate`**: Updates the grid by converting temporarily infected cells back to the infected state.\n\n### Summary\nThis code effectively identifies and contains viral outbreaks on a grid using DFS to track and manage infections. By systematically dismantling the most threatening infected blocks and managing contamination, the algorithm efficiently calculates the number of walls needed to contain the virus.\n\n### Full Code\n\n\n```cpp\nclass Solution {\npublic:\n    // Main function to contain the virus\n    int containVirus(vector<vector<int>>& inf) {\n        int m = inf.size(); // Get the number of rows in the grid\n        int n = inf[0].size(); // Get the number of columns in the grid\n        int ans = FindWalls(m, n, inf); // Start the process to find and build walls\n        return ans; // Return the total number of walls built\n    }\n\n    // Function to find and build walls around the most threatening infection region\n    int FindWalls(int m, int n, vector<vector<int>>& inf) {\n        int ans = 0; // Total walls built\n        int maxima = 0; // Maximum potential spread from a block\n        int start_x = 0; // X coordinate of the most threatening block\n        int start_y = 0; // Y coordinate of the most threatening block\n\n        while (true) { // Loop until there are no more infected regions\n            maxima = 0; // Reset maximum size for this iteration\n            int local_ans = 0; // Walls needed for the current block\n            vector<vector<int>> v(m, vector<int>(n, 0)); // Visited grid for tracking\n\n            // Iterate through the grid to find all infected blocks\n            for (int i = 0; i < m; i++) {\n                for (int j = 0; j < n; j++) {\n                    // If the cell is infected and not visited\n                    if (inf[i][j] == 1 && v[i][j] == 0) {\n                        initialize(v, m, n, inf); // Initialize visited grid\n                        local_ans = blocks(i, j, v, inf, m, n); // Count the size of this block\n                        if (local_ans > maxima) { // Check if it\'s the largest\n                            start_x = i; // Update coordinates for the largest block\n                            start_y = j;\n                        }\n                        maxima = max(maxima, local_ans); // Update the maximum size found\n                    }\n                }\n            }\n\n            // If no infected block is found, exit the loop\n            if (maxima == 0) return ans;\n\n            // Reset visited grid for the next block\n            for (int i = 0; i < m; i++)\n                for (int j = 0; j < n; j++)\n                    v[i][j] = 0;\n\n            // Count the walls needed to contain the largest spread block\n            ans += blockToSpread(start_x, start_y, v, inf, m, n); // Add walls count\n            vector<vector<int>> G(m, vector<int>(n, 0)); // Grid to track dismantling\n            Dismantle(start_x, start_y, inf, G, m, n); // Mark the infected block as walls\n            ContaminateMarking(inf, m, n); // Mark adjacent cells for possible contamination\n            Contaminate(inf, m, n); // Update grid with new infections\n        }\n    }\n\n    // Function to initialize the visited grid\n    void initialize(vector<vector<int>>& v, int m, int n, vector<vector<int>>& inf) {\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                // Mark non-infected cells as unvisited\n                if (inf[i][j] == 0)\n                    v[i][j] = 0;\n            }\n        }\n    }\n\n    // DFS to count the size of the infected block starting from (x, y)\n    int blocks(int x, int y, vector<vector<int>>& v, vector<vector<int>>& inf, int m, int n) {\n        // Out of bounds check\n        if (x < 0 || x >= m || y < 0 || y >= n)\n            return 0; // Invalid cell\n\n        // If already visited, return\n        if (v[x][y] == 1)\n            return 0; // Already counted\n\n        v[x][y] = 1; // Mark the cell as visited\n\n        // If the cell is empty, count it as a potential spread\n        if (inf[x][y] == 0)\n            return 1; // Empty cell, count it\n\n        // If the cell has a wall, it can\'t be counted\n        if (inf[x][y] == -1)\n            return 0; // Wall cell, don\'t count it\n\n        int sum = 0; // To count the size of the block\n        // If the cell is infected, continue DFS to adjacent cells\n        if (inf[x][y] == 1) {\n            sum += blocks(x + 1, y, v, inf, m, n); // Down\n            sum += blocks(x - 1, y, v, inf, m, n); // Up\n            sum += blocks(x, y - 1, v, inf, m, n); // Left\n            sum += blocks(x, y + 1, v, inf, m, n); // Right\n        }\n        return sum; // Return the total count of this block\n    }\n\n    // Count potential spread from a block starting at (x, y)\n    int blockToSpread(int x, int y, vector<vector<int>>& v, vector<vector<int>>& inf, int m, int n) {\n        // Out of bounds check\n        if (x < 0 || x >= m || y < 0 || y >= n)\n            return 0; // Invalid cell\n\n        // If the cell is empty, count it as potential spread\n        if (inf[x][y] == 0) {\n            return 1; // Count empty cell\n        }\n\n        // If already visited, return\n        if (v[x][y] == 1)\n            return 0; // Already counted\n\n        v[x][y] = 1; // Mark the cell as visited\n\n        int sum = 0; // To count potential spread\n        // If the cell is infected, continue to adjacent cells\n        if (inf[x][y] == 1) {\n            sum += blockToSpread(x + 1, y, v, inf, m, n); // Down\n            sum += blockToSpread(x - 1, y, v, inf, m, n); // Up\n            sum += blockToSpread(x, y - 1, v, inf, m, n); // Left\n            sum += blockToSpread(x, y + 1, v, inf, m, n); // Right\n        }\n        return sum; // Return the total count of potential spread\n    }\n\n    // Dismantle the infected block by marking it with walls\n    void Dismantle(int x, int y, vector<vector<int>>& inf, vector<vector<int>>& G, int m, int n) {\n        // Out of bounds check\n        if (x < 0 || x >= m || y < 0 || y >= n)\n            return; // Invalid cell\n\n        // If already processed, return\n        if (G[x][y] == 1)\n            return; // Already processed\n\n        G[x][y] = 1; // Mark this cell as processed\n\n        // If the cell is infected, mark it as a wall\n        if (inf[x][y] == 1) {\n            inf[x][y] = -1; // Mark as wall\n            // Recursively dismantle adjacent cells\n            Dismantle(x + 1, y, inf, G, m, n); // Down\n            Dismantle(x - 1, y, inf, G, m, n); // Up\n            Dismantle(x, y + 1, inf, G, m, n); // Right\n            Dismantle(x, y - 1, inf, G, m, n); // Left\n        }\n    }\n\n    // Mark adjacent cells of infected blocks for contamination\n    void ContaminateMarking(vector<vector<int>>& inf, int m, int n) {\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                // If the cell is infected, mark its empty neighbors\n                if (inf[i][j] == 1) {\n                    ContaminateBlockMarking(i + 1, j, inf, m, n); // Down\n                    ContaminateBlockMarking(i - 1, j, inf, m, n); // Up\n                    ContaminateBlockMarking(i, j + 1, inf, m, n); // Right\n                    ContaminateBlockMarking(i, j - 1, inf, m, n); // Left\n                }\n            }\n        }\n    }\n\n    // Mark an adjacent empty cell as temporarily infected\n    void ContaminateBlockMarking(int x, int y, vector<vector<int>>& inf, int m, int n) {\n        // Out of bounds check\n        if (x < 0 || x >= m || y < 0 || y >= n)\n            return; // Invalid cell\n\n        // If the cell is empty, mark it as temporarily infected\n        if (inf[x][y] == 0)\n            inf[x][y] = -2; // Mark temporarily infected\n    }\n\n    // Convert temporarily infected cells back to infected\n    void Contaminate(vector<vector<int>>& inf, int m, int n) {\n        for (int\n\n i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                // If a cell is temporarily infected, convert it to infected\n                if (inf[i][j] == -2)\n                    inf[i][j] = 1; // Change back to infected\n            }\n        }\n    }\n};\n```\n\n\n
['C++']