Sunday, October 10, 2010

10610 - Gopher and Hawks - UVA

graph search algorithm - BFS

You are given some points in a grid and have to calculate whether you can reach a end point from a start point or not. When you leave a point to reach another point you can just run for m*60 seconds, if you run more you will disappear ;-). So "distance between pi and pk / V < m*60" must satisfy to be sure that you can go from pi to pk, in this way I create adjacency matrix and then easily run a BFS on the graph to find the shortest path from the start point to the end point.
at
Labels:

1 comment:

Subscribe to: Post Comments (Atom)

USACO - Prime Palindromes

I just skimmed the problem statement and panicked of the high boundary of the input, but something inside told me don't worry everyth...

  • 11388 - GCD LCM - UVA
    Mathematics As you can see in the problem description, you have to find numbers a & b such that (a, b) = G and [a, b] = L and also it ...
  • USACO - Prime Cryptarithm
    Prime Cryptarithm The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set ...
  • USACO - Arithmetic Progressions
    Let's think about it, Have you noticed the small boundary of N & M, What can we do with this small boundary? Isn't producing al...