老师这里讲的太快了

Question

老师好

int minTurns[102][102][4], pre[102][102][4][3];
int q[40001][4];   // 0: X  1: Y  2: Direction  3: Turns
q[0][0] = 1;
q[0][1] = 1;
q[0][2] = 0;  // East
q[0][3] = -1;
q[1][0] = 1;
q[1][1] = 1;
q[1][2] = 1;  // South
q[1][3] = -1;

这里没有定义左拐右拐，而且代码中没有注释非常难以理解，能不能再解释一下？
这里定义了很多变量，这样上课很难理解，能不能稍微考虑一下第一次学习的同学。

Answer 1

吉他熊 2022-06-19 15:14:53

感谢你的反馈！

这里我设定的是上下左右的四个方向各走一步的坐标，对于有一定的BFS的基础的同学，应该不会特别难理解，但可能第一次学的同学确实容易看不懂，注释确实是有必要的。我回头更新一下代码注释部分，方便大家学习。

关于你的问题，左拐右拐是和当前朝向相关的。比方说，如果当前朝东走，放到二维数组对应的下标来说就是(0, 1)（先行后列）。然后，我的dx、dy每一位对应的方向也是刻意的，0代表东，1代表南，2代表西，3代表北

这样的话，对于每个方向来说，它左拐就是它的上一个方向（方向-1），右拐就是下一个方向（方向+1），比如对于朝南的时候，左拐就是朝东，右拐就是朝西，那么对应过来，1的左拐就是1-1 = 0，右拐就是1+1 = 2。

但是对于边界情况，比如说朝北，对应3，朝北左拐还好说，对应的朝西是2，可是朝东是0，怎么办呢？实际上，朝东就是(朝北+1) 之后对4取个余数，也就是(3+1) % 4 = 0。如果对于朝东是0，左拐是3，可是0 - 1 = -1，不好办，那么就再+4，变成3，就好办了

所以最后综合起来，左拐就是当前方向+3然后对4取余，右拐就是当前方向+1对4取余

还有哪里不懂的，欢迎提问，你的反馈越多，就越能帮我把课做得更完善，也能帮到其他的同学 :)

• 提问者 huichuan #1

  老师你回复的太快了，大赞；这样解释就完全明白啦，实在感谢！

• 吉他熊 回复 提问者 huichuan #2

  ^_^能帮到你就好！

Answer 2

提问者 huichuan 2022-06-19 14:45:40

还有底下这里

1. int id = (dir + 3 - i * 2) % 4;

2. 这里能不能再稍微解释一下

• 吉他熊 #1

  其实这里就是控制左拐和右拐两种情况的循环。
  i是一个0到1的循环，那么i = 0的时候，+3 - i * 2 = +3，对应左拐，i = 1的时候，+3 - i * 2 = +1，对应右拐
  不知道这么解释是否明白一些？

• 提问者 huichuan 回复 吉他熊 #2

  还有个小问题，关于q数组的初始化是怎么理解的呀？ 这一块还是没有特别理解哈

• 吉他熊 回复 提问者 huichuan #3

  q数组是这样的——
  q是用来模拟一个队列，用head和tail分别代表队列的头和尾。没有用queue是为了兼容使用C的同学，因为C里面没有STL可用。
  q的四位分别代表x坐标，y坐标，当前朝向，以及拐弯次数。这里用struct结构体应该能更清楚一些
  那么一开始我们位于左上角，所以只能朝东或者朝南，对应的就是两种情况：
  1. 坐标(1, 1)，朝向0（东），拐弯次数-1（之所以用-1是因为拐弯数=线段数-1，而且扩展一次状态，拐弯数就会+1，拐弯次数同时也可以看做BFS的层数）
  2. 坐标(1,1)，朝向1（南），拐弯次数-1
  这两个情况就作为BFS的两个起始状态放入队列中，q[0][0..3]代表情况1，q[1][0..3]代表情况2
  
  大概就是这样

点开查看后面4条评论