HBC24053减成一,差分,枚举[USACO 2017 Jan G]Cow Navigation题解

回忆凄美了谁算法基础篇 2023-11-20 12:02:02 53 0

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

Bessie has gotten herself stuck on the wrong side of Farmer John's barn again, and since her vision is so poor, she needs your help navigating across the barn. The barn is described by an N×NNtimes NN×Ngrid of square cells , some being empty and some containing impassable haybales. Bessie starts in the lower-left corner and wants to move to the upper-right corner . You can guide her by telling her a sequence of instructions, each of which is either "forward", "turn left 90 degrees", or "turn right 90 degrees". You want to issue the shortest sequence of instructions that will guide her to her destination. If you instruct Bessie to move off the grid or into a haybale, she will not move and will skip to the next command in your sequence. Unfortunately, Bessie doesn't know if she starts out facing up or right . You need to give the shortest sequence of directions that will guide her to the goal regardless of which case is true. Once she reaches the goal she will ignore further commands.

Bessie has gotten herself stuck on the wrong side of Farmer John's barn again, and since her vision is so poor, she needs your help navigating across the barn. The barn is described by an N×NNtimes NN×N grid of square cells (2≤N≤202 leq N leq 202≤N≤20), some being empty and some containing impassable haybales. Bessie starts in the lower-left corner (cell 1,1) and wants to move to the upper-right corner (cell N,N). You can guide her by telling her a sequence of instructions, each of which is either "forward", "turn left 90 degrees", or "turn right 90 degrees". You want to issue the shortest sequence of instructions that will guide her to her destination. If you instruct Bessie to move off the grid (i.e., into the barn wall) or into a haybale, she will not move and will skip to the next command in your sequence. Unfortunately, Bessie doesn't know if she starts out facing up (towards cell 1,2) or right (towards cell 2,1). You need to give the shortest sequence of directions that will guide her to the goal regardless of which case is true. Once she reaches the goal she will ignore further commands.