P1518 [USACO2.4] The Tamworth Two

Two cows have escaped into the forest. Farmer John begins to pursue them using his expert technique. Your task is to simulate their behavior (the cows and John). The chase takes place on a $10 \times 10$ grid. Each cell can be: an obstacle, the two cows (they always stay together), or Farmer John. The cows and Farmer John may occupy the same cell (when they meet), but neither can enter a cell with an obstacle. A cell can be: - `.` empty ground; - `*` obstacle; - `C` the two cows; - `F` Farmer John. Here is an example map: ```plain *...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*...... ``` The cows wander the map in a fixed way. Each minute, they either move forward or turn. If the cell directly ahead is not blocked (the map border also counts as a blockage), they advance one cell in their current direction. Otherwise, they spend that minute turning 90 degrees clockwise. They never move off the map. Farmer John knows the cows' movement rule and moves in exactly the same way. The cows and Farmer John move simultaneously each minute. If they pass through each other during a move but do not end up in the same cell at the end of that minute, that does not count as a meeting. When they occupy the same cell at the end of some minute, the chase ends. Read ten lines describing the map. Each line contains exactly 10 characters, with meanings as defined above. There is exactly one `F` and one `C`. `F` and `C` do not start in the same cell. Compute how many minutes Farmer John needs to catch the cows, assuming both the cows and Farmer John initially face north (up). If John and the cows will never meet, output 0.

The input consists of ten lines, each with 10 characters, describing the map as above.

Output a single integer: the number of minutes Farmer John needs to catch the cows. If he cannot catch them, output 0.

Translation from NOCOW. USACO 2.4. Translated by ChatGPT 5