Breaking Bad | MatCom Online Grader

The 2025 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

B - Breaking Bad

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

<div style="text-align: justify">
Axel White and Lexa Pinkman are cooking some crystal in their lab... I mean, they are making high-quality and refined crystal panels for decorative purposes through a process of heating and hitting.

Axel, the artist of the duo, has a very specific vision of what constitutes a "beautiful crystal panel". For him, beauty lies in the process. A panel is crafted using a delicate heating process that starts at the top-left corner, coordinate $(1,1)$. During this process, the heating head can only move down (from $(i,j)$ to $(i+1,j)$) or right (from $(i,j)$ to $(i,j+1)$). For a panel to be considered "beautiful", there must exist at least one valid "heating path" that, in addition to following the movement rules, passes through all the essential decorative cells that Axel has designed.

Lexa, on the other hand, is more pragmatic and sometimes a bit chaotic. Her goal is to sabotage the production with the minimum possible effort. She can hit the panel in certain areas to create fractures, making it impossible for the heating head to pass through them. Her task is to find the cheapest way to create a set of fractures such that no valid "heating path" can be completed, thus rendering the panel "not beautiful".

**Panel Specification:**

The crystal panel is represented as an $N\times N$ grid. Each cell $(i,j)$ on the panel has a type and a cost (effort, resources, etc.) associated with fracturing it.

There are $5$ types of cells on the panel: </div>

- Type $0$ (Impurity): Zones with factory defects. The heating head cannot pass through here. They are already "fractured", and no interaction is possible.
- Type $1$ (Standard Crystal): Normal zones of the panel. Lexa can hit them to create a fracture. The cost of fracturing the cell $(i,j)$ is the cost specified for that cell.
- Type $2$ (Decorative Cell): Key points in Axel's design. For the panel to be "beautiful", the heating path must pass through all of these cells. Lexa can also fracture these cells by paying their corresponding cost. If a single decorative cell is fractured, it becomes impassable, and therefore no valid path can exist.
- Type $3$ (Reinforced Cell): Zones of tempered crystal. The heating head can pass through them, but Lexa cannot fracture them. They are impervious to her strikes.
- Type $4$ (Reinforced Decorative Cell): The centerpiece of the design. These are decorative cells that are also reinforced. The heating path must pass through them, and Lexa cannot fracture them.

<div style="text-align: justify">
Your task is to help Lexa. You must find a set of type $1$ or type $2$ cells to fracture such that no valid heating path exists starting from $(1,1)$. The goal is for the total cost of the fractures (the sum of the costs of the selected cells) to be the minimum possible.
</div>

Input