P1649 [USACO07OCT] Obstacle Course S

Consider an N x N (1

Line 1: A single integer: N Lines 2..N + 1: Line i+1 represents row i of the field with N characters as above (i.e., '.', 'x', 'A', and 'B'); no spaces are present on a line

Line 1: A single integer, the minimum number of turns the cow must make in a traversal

The cow must make at least 2 turns: For example, the cow may start by facing south, move south, turn to face west, move west, move west, then turn to face south, and finally move south into the B square.