Problem 1457. USC Spring 2013 ACM: Walking on Thin Ice
This Challenge is to solve the USC Spring 2013 ACM Contest Problem E, Walking on Thin Ice.
The Rooster is crossing to the other side of the frozen river. Minimize his distance traveled on thin ice given a river width (w) and polygons(polycell) that denote non-thin ice regions. Start anywhere on the x-axis(y=0) and finish by reaching y=w.
Input:
w=120
polycell={[0 10 0 90 50 50 100 90 100 10] [0 110 100 110 50 70]};
Output: 35.6174
The only USC competition solver(45 minutes): Cao's C solution
Theory:
Traveling Salesman Optimum Route. (Matlab one line while)
Create Interconnect Matrix
Calculate Route/Distances between Good-Ice using Polygon to Polygon distance function.
Polygon to Polygon minimum distance uses minimum Point to Line Segment function.
Related Challenges:
Solution Stats
Solution Comments
Show commentsProblem Recent Solvers2
Suggested Problems
-
Find the longest sequence of 1's in a binary sequence.
5801 Solvers
-
321 Solvers
-
Set the array elements whose value is 13 to 0
1338 Solvers
-
Eliminate Polysyllabics: Long live short words!
106 Solvers
-
120 Solvers
More from this Author294
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!