中级农民
- 积分
- 109
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2018-7-5
- 最后登录
- 1970-1-1
|
先建立一个1对多的map,next(i,j) = {(i.,j) 下一步能到达的坐标}。
利用这个next mapping, 反过来 建立mapping, prev(i,j) = {走一步能到达(i,j)的坐标}
有了这个准备数据 就可以DFS - 从右下开始,找到一步到达右下的所有坐标,赋值1 (步);对这些值为1的坐标,找到他们的上一步,如果没被赋值过的,赋值2;然后继续这样赋值3,4.。。直到找到左上坐标,其赋值就是解; 如果拓展到停止还没到左上 则无解。
|
|