{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003eLiaoning ship, which named after a province of China, is the first aircraft carrier commissioned into the People\u0027s Liberation Army Navy. It was bought from Ukraine as a stripped hulk and was rebuilt by China as an important part of China’s blue water Navy plan. Liaoning ship has sailed far into the Pacific Ocean for serval times, which shows the power and resolve of China to defend her integrity of territory.\u003c/p\u003e \n \u003cp\u003eNow Liaoning ship is on a new voyage to the Atlantic Ocean for a maneuver! The vast maneuver region on the ocean can be seen as an n×n grid which has n×n crosspoints. Each crosspoint stands for a check point of the maneuver region. Liaoning starts from the bottom-left check point whose coordinate is (0,0), and its destination is the upper-right checkpoint whose coordinate is (n-1,n-1). The positive side of the x axis points to the right, and the positive side of the y axis points up. All check points’ coordinates are integral. During each move, Liaoning can go from one check point to its adjacent 8 check points \u003cstrong\u003ealong a straight line\u003c/strong\u003e, and each move takes Liaoning one day. Some check points are not available to go due to the bad weather. And, as you know, on the Atlantic Ocean, there is a Bermuda Triangle in which many ships and planes were missing. Liaoning can’t take risk to go into that triangle. Of course, Liaoning can’t go outside the maneuver region. Please figure out a route for Liaoning to reach its destination as soon as possible.\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003eThere are no more than 30 test cases.\u003c/p\u003e \n \u003cp\u003eFor each case:\u003c/p\u003e \n \u003cp\u003eThe first line is an integer n( 2 \u0026lt;\u003d n \u0026lt;\u003d 20), meaning that the maneuver region is an n×n grid.\u003c/p\u003e \n \u003cp\u003eThe seconds line contains six float numbers x\u003csub\u003e1\u003c/sub\u003e,y\u003csub\u003e1\u003c/sub\u003e,x\u003csub\u003e2\u003c/sub\u003e,y\u003csub\u003e2\u003c/sub\u003e,x\u003csub\u003e3\u003c/sub\u003e,y\u003csub\u003e3\u003c/sub\u003e( -100 \u0026lt;\u003d x\u003csub\u003e1\u003c/sub\u003e,y\u003csub\u003e1\u003c/sub\u003e,x\u003csub\u003e2\u003c/sub\u003e,y\u003csub\u003e2\u003c/sub\u003e,x\u003csub\u003e3\u003c/sub\u003e,y\u003csub\u003e3\u003c/sub\u003e \u0026lt;\u003d 100) which have at most 2 digits after the decimal point, indicating the coordinates of the vertices of Bermuda Triangle are (x\u003csub\u003e1\u003c/sub\u003e,y\u003csub\u003e1\u003c/sub\u003e), (x\u003csub\u003e2\u003c/sub\u003e,y\u003csub\u003e2)\u003c/sub\u003e and (x\u003csub\u003e\u003cstrong\u003e3\u003c/strong\u003e\u003c/sub\u003e,y\u003csub\u003e3\u003c/sub\u003e). Liaoning ship can’t go into that triangle, but going along its edges or touching its vertices are allowed.\u003c/p\u003e \n \u003cp\u003eThen an n×n character matrix consists of ‘.’ and ‘#’ follows, indicating the weather condition of all check points. ‘.’ Means good weather and ‘#’ means bad weather. The bottom-left character stands for the weather of check point (0,0), the character on the right side of it stands for (1,0), and the upper-right character stands for (n-1,n-1). \u003c/p\u003e \n \u003cp\u003eIt is guaranteed that check point (0,0) is not inside the Bermuda Triangle or on the edges of the triangle.\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003e\u003cspan\u003eFor each test case, print the minimum days Liaoning ship needs to reach its destination. If it is impossible for Liaoning to reach its destination, print -1 instead.\u003c/span\u003e\u003c/p\u003e \n \u003c/div\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e3\r\n0.5 1.5 1.5 1.5 1 0.5\r\n.#.\r\n...\r\n..#\r\n3\r\n0.5 1.5 1.5 1.5 1 0.5\r\n.#.\r\n..#\r\n..#\r\n\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003e3\r\n-1\r\n\u003c/pre\u003e \n "}}]}