Sagheer, the Hausmeister

题意翻译

# Sagheer, the Hausmeister ## 题目大意 有一栋楼房，里面有很多盏灯没关，为了节约用电Sagheer决定把这些灯都关了。 这楼有 n 层，最左边和最右边有楼梯。每一层有 m 个房间排成一排。这栋楼可以被表示成一个 n 行 m + 2 列的矩阵，其中每行第一个和最后一个格点表示楼梯， 剩余 m 个格点表示房间。 现在Sagheer在最底层的最左边楼梯，他想要关掉所有的灯。他每次可以走到相邻的房间，如果在楼梯口可以上下楼梯。他打算关掉所有开着的灯，在他没有将一层的所有灯都关闭前他不会上楼。现在求他最少需要走多少步可以关闭所有灯。 注意Sagheer不需要返回原处，最终可以停留在任意一个地方。 ## 输入格式 第一行包含两个整数 n 和 m (1 ≤ n ≤ 15 并且 1 ≤ m ≤ 100) — 表示层数和每层的房间数。 之后 n 行描述这栋楼。每行包含一个长度为 m + 2 的字符串表示这层楼的情况，如果值是1表示灯亮着，否则表示灯没亮。 保证每个字符串首尾位都为0。 ## 输出格式 输出一个整数，表示熄灭所有灯所需的最少步数。 ## 样例 #1 ### 样例输入 #1 ``` 2 2 0010 0100 ``` ### 样例输出 #1 ``` 5 ``` ## 样例 #2 ### 样例输入 #2 ``` 3 4 001000 000010 000010 ``` ### 样例输出 #2 ``` 12 ``` ## 样例 #3 ### 样例输入 #3 ``` 4 3 01110 01110 01110 01110 ``` ### 样例输出 #3 ``` 18 ```

题目描述

Some people leave the lights at their workplaces on when they leave that is a waste of resources. As a hausmeister of DHBW, Sagheer waits till all students and professors leave the university building, then goes and turns all the lights off. The building consists of $ n $ floors with stairs at the left and the right sides. Each floor has $ m $ rooms on the same line with a corridor that connects the left and right stairs passing by all the rooms. In other words, the building can be represented as a rectangle with $ n $ rows and $ m+2 $ columns, where the first and the last columns represent the stairs, and the $ m $ columns in the middle represent rooms. Sagheer is standing at the ground floor at the left stairs. He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off. Of course, Sagheer must visit a room to turn the light there off. It takes one minute for Sagheer to go to the next floor using stairs or to move from the current room/stairs to a neighboring room/stairs on the same floor. It takes no time for him to switch the light off in the room he is currently standing in. Help Sagheer find the minimum total time to turn off all the lights. Note that Sagheer does not have to go back to his starting position, and he does not have to visit rooms where the light is already switched off.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1<=n<=15 $ and $ 1<=m<=100 $ ) — the number of floors and the number of rooms in each floor, respectively. The next $ n $ lines contains the building description. Each line contains a binary string of length $ m+2 $ representing a floor (the left stairs, then $ m $ rooms, then the right stairs) where $ 0 $ indicates that the light is off and $ 1 $ indicates that the light is on. The floors are listed from top to bottom, so that the last line represents the ground floor. The first and last characters of each string represent the left and the right stairs, respectively, so they are always $ 0 $ .

输出格式

Print a single integer — the minimum total time needed to turn off all the lights.

输入输出样例

输入样例 #1

2 2
0010
0100

输出样例 #1

5

输入样例 #2

3 4
001000
000010
000010

输出样例 #2

12

输入样例 #3

4 3
01110
01110
01110
01110

输出样例 #3

18

说明

In the first example, Sagheer will go to room $ 1 $ in the ground floor, then he will go to room $ 2 $ in the second floor using the left or right stairs. In the second example, he will go to the fourth room in the ground floor, use right stairs, go to the fourth room in the second floor, use right stairs again, then go to the second room in the last floor. In the third example, he will walk through the whole corridor alternating between the left and right stairs at each floor.

题意翻译

# Sagheer, the Hausmeister ## 题目大意 有一栋楼房，里面有很多盏灯没关，为了节约用电Sagheer决定把这些灯都关了。 这楼有 n 层，最左边和最右边有楼梯。每一层有 m 个房间排成一排。这栋楼可以被表示成一个 n 行 m + 2 列的矩阵，其中每行第一个和最后一个格点表示楼梯， 剩余 m 个格点表示房间。 现在Sagheer在最底层的最左边楼梯，他想要关掉所有的灯。他每次可以走到相邻的房间，如果在楼梯口可以上下楼梯。他打算关掉所有开着的灯，在他没有将一层的所有灯都关闭前他不会上楼。现在求他最少需要走多少步可以关闭所有灯。 注意Sagheer不需要返回原处，最终可以停留在任意一个地方。 ## 输入格式 第一行包含两个整数 n 和 m (1 ≤ n ≤ 15 并且 1 ≤ m ≤ 100) — 表示层数和每层的房间数。 之后 n 行描述这栋楼。每行包含一个长度为 m + 2 的字符串表示这层楼的情况，如果值是1表示灯亮着，否则表示灯没亮。 保证每个字符串首尾位都为0。 ## 输出格式 输出一个整数，表示熄灭所有灯所需的最少步数。 ## 样例 #1 ### 样例输入 #1 ``` 2 2 0010 0100 ``` ### 样例输出 #1 ``` 5 ``` ## 样例 #2 ### 样例输入 #2 ``` 3 4 001000 000010 000010 ``` ### 样例输出 #2 ``` 12 ``` ## 样例 #3 ### 样例输入 #3 ``` 4 3 01110 01110 01110 01110 ``` ### 样例输出 #3 ``` 18 ```