Black Shapes

Logical Breakdown

• [ ] Subproblem Identification:
• [ ] Optimal Substructure:
• [ ] Constraint Handling: (e.g., Modulo \(10^9 + 7\))
• [ ] Optimization: (Matrix Exponentiation if 'A' is huge)

---

Mathematical Rigor

State Definition

Let \(dp[i]\) be the state for the \(i\)-th subproblem.

Recurrence Relation

\[ dp[i] = ... \]

---

Visualization

graph TD A["Current State"] --> B["Previous State 1"] A --> C["Previous State 2"]

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Iterative DP	\(O(N)\)	\(O(1)\)

---

Code Reference

package com.dsa.graphs;

import java.util.*;

/* * ============================================================================================ * PROBLEM: Black Shapes * ============================================================================================ * * --------------------- * 1. Problem Description * --------------------- * Given a matrix of characters 'X' (Black) and 'O' (White). * Find the number of black shapes. * A black shape is a connected component of 'X's. * Connectivity: Horizontal and Vertical neighbors. * * --------------------- * 2. Logical Breakdown * --------------------- * Identical to "Number of Islands". * * Algorithm: * 1. Loop through matrix. * 2. If cell == 'X' and not visited: * - Increment Shape Count. * - Call DFS(r, c) to flood-fill all connected 'X's. * * DFS(r, c): * - Mark (r, c) as visited. * - For each direction (Up, Down, Left, Right): * - If neighbor is valid 'X' and unvisited, recurse. * * --------------------- * 3. Complexity * --------------------- * Time: O(N * M) * Space: O(N * M) for recursion stack. * * ============================================================================================ / public class BlackShapes { public int solve(int A) { // TODO: Implement solution return 0; }

public int black(String[] input2) {
    return 1;
}

}