Company: Samsung
Difficulty: medium
Rock Climbing Difficulty Problem Description Mr. K has a strong passion for rock-climbing. Having completed several courses, he now seeks to conquer a particularly tough one. He has obtained a map of the course in advance and wishes to prepare himself to successfully complete it. The rock map is defined by its height N and width M . In the map, a ' ~ ' (represented as ' 1 ' in input) signifies a spot where a foot can be placed, while an empty space (represented as ' 0 ' in input) means there is no space for a foot. Movement rules are as follows: Horizontal Movement: If ' ~ ' spots exist sequentially on the same height, Mr. K can move freely horizontally between them. However, if ' ~ ' spots are more than one space apart horizontally, moving between them is impossible due to safety reasons. Vertical Movement: From the current location, if a ' ~ ' spot exists directly in the level above or below, Mr. K can safely move up or down by using his equipment and physical strength. The crucial a