시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 101 | 74 | 65 | 70.652% |
Finally, after years of pleading, Farmer John relented and has purchased roller skates for the entire herd of cows. A large bit of the farm is just great for roller-skating, but several parcels have just way too many rocks and are unpassable on skates.
The farm is conveniently reprssented as a grid of squares with R (1 <= R <= 113) rows and C (1 <= C <= 77) columns. Bessie finds herself at square (1,1) near feeding time and wants to get back to barn which is located at square (R,C). She knows there is at least one way to do so by skating to adjacent squares (but not on the diagonal) that don't contain rocks. Find and display any path that Bessie can follow to get to the barn.
Consider R=5, C=8 farm layout below on the left, where '*' means "too many rocks here". The right-hand map shows one possible path Bessie might use to get to the barn in the lower right corner:
12345678 12345678 1 B.*...** 1 @@*@@@** 2 *.*.*.** 2 *@*@*@** 3 *...*... 3 *@@@*@@@ 4 *.*.*.*. 4 *.*.*.*@ 5 ....*.*B 5 ....*.*@
5 8 ..*...** *.*.*.** *...*... *.*.*.*. ....*.*.
1 1 1 2 2 2 3 2 3 3 3 4 2 4 1 4 1 5 1 6 2 6 3 6 3 7 3 8 4 8 5 8