Water Quality Detector Connectivity

Xiaoming has a riverbed of size \(2\times n\). Some water quality detectors have already been installed on certain cells. The rows are numbered 1 and 2, and the columns are numbered from 1 to \(n\). A cell may or may not have a detector. Two detectors are considered connected if they are adjacent horizontally or vertically. Note that connectivity is transitive; that is, if detector A is connected to B, and B to C, then A is also connected to C.

Before proceeding, Xiaoming would like to add additional detectors so that all detectors (both the originally installed ones and the newly added ones) form a single connected group. What is the minimum number of detectors that need to be added?

Input Format

The input consists of three lines:

• The first line contains a single integer \(n\) \( (1 \leq n \leq 10^5) \) representing the number of columns.
• The second line is a string of length \(n\) consisting of characters '0' and '1'. The \(i\)-th character indicates whether there is a detector in the top cell of column \(i\) ('1' means a detector is present, '0' means it is absent).
• The third line is a string of length \(n\) in the same format for the bottom row.

Output Format

Output a single integer: the minimum number of detectors to be added so that all detectors become connected. If there are no detectors or they are already connected, output 0.

Problem Explanation

You are given a \(2\times n\) grid with some cells initially containing detectors. In the final configuration, you are allowed to add detectors to any cell. However, you may not remove any originally installed detectors. Two detectors in adjacent cells (sharing a common side) are connected. The final configuration must yield a single connected component that contains every detector (both original and added).

Hint: It is always optimal to "fill in" every column between the leftmost and rightmost columns that originally contain a detector, choosing for each column a set of detectors (either only the top, only the bottom, or both) to guarantee that every consecutive pair of columns share a detector in the same row. For each column, if there is an originally installed detector, you must include that cell in your final state. For an empty cell you may decide to add a detector with a cost of 1. Finally, make sure that adjacent columns have at least one row in common that contains a detector.

The states for each column can be defined as follows:

• State 0: Only the top cell has a detector.
• State 1: Only the bottom cell has a detector.
• State 2: Both cells have detectors.

If a column originally has a detector in a certain cell, then the final state for that column must include that cell. The cost for a column is defined as the number of detectors that you add in that column. For example, if a column originally is empty and you choose state 0 then you add 1 detector; if you choose state 2 then you add 2 detectors. Use dynamic programming over the columns between the leftmost and rightmost mandatory columns to compute the minimum total cost while ensuring adjacent columns have a common row with a detector.

inputFormat

The input consists of three lines. The first line contains an integer \(n\). The second and third lines each contain a string of length \(n\) made up of '0' and '1', representing the top and bottom rows respectively. '1' indicates a detector is already present and '0' indicates an empty cell.

outputFormat

Output a single integer — the minimum number of detectors that need to be added so that the final configuration (including both the original and the added detectors) forms a single connected group. If the detectors are already connected (or there are no detectors), output 0.

sample

3
100
001

2