Knight Shortest Path II

LintCode LeetCode DynamicProgramming

submit 1:

ac:

这道题看的答案，起初一直不知道该怎么初始化每个棋盘的值，以及如何确定函数，还有遇到障碍应该怎么办（想到过设置为Integer.MAX_VALUE，但没有想到最后如何判断能不能reach）。看了答案，发现无非是我的思维厌倦完整具细的分类讨论，缺乏耐心。不过除开分类讨论，确定if (!grid[i][j]) 这个条件也很关键，很巧妙地解决了遇到barrier的情况，因为if语句下面的赋值操作只有当棋盘该位置不是障碍才能进行，所以最后障碍点的值都是Integer.MAX_VALUE. 并且函数语句的判断语句也要确定上一步是不是走到了barrier, 只有上一步不是障碍的情况，这一步才可能被重新赋值，不然就依然会保持Integer.MAX_VALUE. 了解到了这一点，就很好判断最后能否reach到棋盘右下角了。如果无法到达这一点，或者只有经过障碍才能到达这一点，那么这一点的值就会是Integer.MAX_VALUE,这时候返回-1就好了。