ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1119. Metro

java AC code
Posted by esbybb 14 Jun 2015 17:00
Messages should not contain correct solutions.

i use matrix of costs, each step set value of the cell as minimal of the

previous vertical cost + 100,
previous horizontal cost + 100,
previous diagonal cost + 100*sqrt(2)

the answer is Math.round(cost[M][N])

p.s.
cycle is organized from 1 to n, 1 to m inclusively

Edited by author 14.06.2015 17:09
Re: java AC code
Posted by esbybb 14 Jun 2015 17:15
by default diagonal cost is set to MAX_VALUE, it is updated in case of a[i][j]=true, where a is a matrix of allowed to be crossed through diagonally cells
Re: java AC code
Posted by esbybb 14 Jun 2015 17:28
also column with index 0 is populated incrementally (cost[0][0]=0, cost[1][0]=100, cost[2][0]=200..)
as well as row with index 0 before the main nested loop starts