From ASMBits


You are in a city with a grid-like design (like Manhattan) and need to get to the nearest subway station. You are given a map that indicates the locations of subway stations. You are currently at the center of the map. Find the distance to the closest subway station, measured using manhattan distance (sum of horizontal and vertical distances, because you need to walk along the grid).

The map is an array of bytes, of width columns (numbered 0 to width-1) and height rows (numbered 0 to height-1). Bytes are arranged in row-major order (i.e., element (x,y) is located at offset x + y × width). Each byte is non-zero if there is a subway station at that location, or zero if there is not. You are at column W/2 and row H/2 (the center of the map). The map will be at least 1×1 in size and at most 107 cells in size.

Example: In the following 5×1 map, the nearest subway station is 1 unit away (to the right). You are at x=2 and y=0 (5/2 = 2, and 1/2 = 0). (There is another subway station 2 units to the left, but it isn't the closest one),

1 0 0 1 0

Return the manhattan distance to the nearest subway station. If there are no subway stations, return -1.

int manhattan (int width, int height, char* map);

Expected solution length: Around 30 lines.

Sample Input

1 0 0 1 0 (width=5, height=1)

Sample Output


Write your solution here

Upload a source file...