Consider a grid pattern withn{n}n rows andm{m}mcolumns. There are(n+1)×(m+1)(n+1)times(m+1)(n+1)×(m+1) grid points in total which is the intersections ofn+1{n+1}n+1 horizontal lines andm+1{m+1}m+1 ver
Consider a grid pattern with n{n}n rows and m{m}m columns. There are (n+1)×(m+1)(n+1)times(m+1)(n+1)×(m+1) grid points in total which is the intersections of n+1{n+1}n+1 horizontal lines and m+1{m+1}m+1 vertical lines. We number the horizontal lines from 0{0}0 to n{n}n from top to bottom. We number the vertical lines from 0{0}0 to m{m}m from left to right. The intersection of horizontal line i{i}i and vertical line j{j}j is named (i,j){(i, j)}(i,j) (0≤i≤n,0≤j≤m)(0le ile n, 0le jle m)(0≤i≤n,0≤j≤m). There are some constraints when you travel in the grid world. When you are located at point (x,y){(x,y)}(x,y), you can choose a destination (x′,y′){(x',y')}(x′,y′) and walk to it along the line segment between (x,y){(x, y)}(x,y) and (x′,y′){(x', y')}(x′,y′). We call this operation a walk. A walk is forbidden if there exists another grid point different from (x,y){(x, y)}(x,y) and (x′,y′){(x', y')}(x′,y′) lying on the line segment between them. You can walk as many times as you want but the directions of two consecutive walks cannot be the same. (Specifically, if you walk from (x0,y0){(x_0, y_0)}(x0,y0) to (x1,y1){(x_1, y_1)}(x1,y1) and then walk from (x1,y1){(x_1, y_1)}(x1,y1) to (x2,y2){(x_2, y_2)}(x2,y2), you must make sure that (x0−x1)(y1−y2)≠(x1−x2)(y0−y1)(x_0-x_1)(y_1-y_2)neq (x_1-x_2)(y_0-y_1)(x0−x1)(y1−y2)=(x1−x2)(y0−y1).) The length of a walk from (x,y){(x, y)}(x,y) to (x′,y′){(x', y')}(x′,y′) is defined as the Euclidean distance between the two endpoints, (x−x′)2+(y′−y)2sqrt{(x-x')^2+(y'-y)^2}(x−x′)2+(y′−y)2. Starting from (0,0){(0,0)}(0,0) ,you are planning to arrive at (n,m){(n,m)}(n,m) by several walks. Because of the annoying rules, you may need some turning points to achieve your goal. Please find the minimum total length of your walks.
