USACO analysis
Mark Chen |
25 Nov 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
Problem 3. Cow Navigation
Problem Summary
Bessie is in the barn of John. The barn has a size of $N\times N$, and some of the square cells are impassable. Bessie starts in the lower-left corner (cell 1, 1) and wants to move to the right corner (cell N, N).
In each second, Bessie can either go forward, turn left, or turn right. If one instruction let it enter an impassable square, it will skip through that instruction. At the beginning, Bessie doesn’t know if she starts out facing up or facing left. 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.
Proposed Solution
The difficult point in this problem is that we don’t know whether Bessie starts with which position and we have to make sure it can arrive at the destination. Since in each situation, the series of instructions used are the same, we can apply BFS on each situation simultaneously.
In this BFS, each state will have two “sub-state”, which represent the position and direction of Bessie when start pointing upward and pointing rightward. We can also apply dynamic programming on this problem - if a set of instruction can reach the same state with shorter length, we should use the shorter instruction series.
We will construct a table with size $N\times N \times 4 \times N \times N \times 4$. The first part $N\times N \times 4$ is the DP table for first sub-state. The second part of table is the DP-table for second sub-state.
The update of DP table and state transition of BFS will follow these rules:
- \[T[S_1, S_2] = \min{(T[S_1, S_2], T[S_1', S_2'] + 1)}\]
- \[Update(S_1, S_2) = S_1, S_2' \text{ if $S_1$ is at final state}\]
- \[Update(S_1, S_2) = S_1',S_2 \text{ if the update will let $S_2$ get into impassable square}\]
Time Complexity Analysis
Therefore, we will search through a graph with $O(N^4)$ nodes. (For each sub-state, there are $N^2$ nodes, though for most of the time, the sub-states has same position, the overall upper bound is $O(N^4)$). Since $0\leq N\leq 20$, the proposed solution will be fast enough.
