[Solution] Cleaning Robot solution codeforces

Cleaning Robot solution codeforces – Consider a hallway, which can be represented as the matrix with 22 rows and 𝑛n columns. Let’s denote the cell on the intersection of the 𝑖i-th row and the 𝑗j-th column as (𝑖,𝑗)(i,j). The distance between the cells (𝑖1,𝑗1)(i1,j1) and (𝑖2,𝑗2)(i2,j2) is |𝑖1𝑖2|+|𝑗1𝑗2||i1−i2|+|j1−j2|.

Table of Contents

[Solution] Cleaning Robot solution codeforces

There is a cleaning robot in the cell (1,1)(1,1). Some cells of the hallway are clean, other cells are dirty (the cell with the robot is clean). You want to clean the hallway, so you are going to launch the robot to do this.

After the robot is launched, it works as follows. While at least one cell is dirty, the robot chooses the closest (to its current cell) cell among those which are dirty, moves there and cleans it (so the cell is no longer dirty). After cleaning a cell, the robot again finds the closest dirty cell to its current cell, and so on. This process repeats until the whole hallway is clean.

However, there is a critical bug in the robot’s program. If at some moment, there are multiple closest (to the robot’s current position) dirty cells, the robot malfunctions.

You want to clean the hallway in such a way that the robot doesn’t malfunction. Before launching the robot, you can clean some (possibly zero) of the dirty cells yourself. However, you don’t want to do too much dirty work yourself while you have this nice, smart (yet buggy) robot to do this. Note that you cannot make a clean cell dirty.

Calculate the maximum possible number of cells you can leave dirty before launching the robot, so that it doesn’t malfunction.

[Solution] Cleaning Robot solution codeforces

The first line contains one integer 𝑛n (2𝑛21052≤n≤2⋅105) — the number of columns in the hallway.

Then two lines follow, denoting the 11-st and the 22-nd row of the hallway. These lines contain 𝑛n characters each, where 0 denotes a clean cell and 1 denotes a dirty cell. The starting cell of the robot (1,1)(1,1) is clean.

Output

Print one integer — the maximum possible number of cells you can leave dirty before launching the robot, so that it doesn’t malfunction.

Examples
input

Copy
2
01
11

[Solution] Cleaning Robot solution codeforces

Copy
2
input

Copy
2
01
01
output

Copy
2
input

Copy
4
0101
1011
output

Copy
4
input

Copy
4
0000
0000
output

Copy
0

[Solution] Cleaning Robot solution codeforces

Copy
5
00011
10101
output

Copy
4
input

Copy
6
011111
111111
output

Copy
8
input

Copy
10
0101001010
1010100110
output

Copy
6

[Solution] Cleaning Robot solution codeforces

In the first example, you can clean the cell (1,2)(1,2), so the path of the robot is (1,1)(2,1)(2,2)(1,1)→(2,1)→(2,2).

In the second example, you can leave the hallway as it is, so the path of the robot is (1,1)(1,2)(2,2)(1,1)→(1,2)→(2,2).

In the third example, you can clean the cell (1,2)(1,2), so the path of the robot is (1,1)(2,1)(2,3)(2,4)(1,4)(1,1)→(2,1)→(2,3)→(2,4)→(1,4).

In the fourth example, the hallway is already clean. Maybe you have launched the robot earlier?

For Solution

“Click Here”

Leave a Comment