为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/ttwo
目录 |
[编辑] 分析
简单的模拟 还是KISS原则，地图的size是10 X 10，那么无论对于Farmer John抑或是Cow，每个点的状态有且仅有上，下，左，右 4 种（分别4种），也就是说，对于Framer John和Cow，每个 点最多走4次，于是在地图上Farmer John 和 Cow 最多走 10*10*4 = 400 次，约定 fstep 记录Farmer John 走的步数，cstep 记录 Cow 走的步数，显然不相遇的情况就是 ( fstep>400 || cstep>400 )，值得注意的是，改变方向也需要耗费 1 minutes ！
简单的模拟
需要记录方向和坐标，进行模拟，直到相遇。如何判断永远不相遇呢？
状态只有(10*10*4)400种，两个人最多(400*400)160000种，也就是说，如果超过160000步，那么肯定会出现有的状态出现了2次以上，那么就肯定是一个死循环，永远不会相遇。
判断无解也可以通过判断当前状态是否出现过——使用源码中until的前两个条件即可。
其实160000种状态可以用一个6维bool数组存起来，不会超。当状态重复出现就是不可能相遇了。
直接模拟。
个人认为，判断是否能够到达，只需从‘F’开始搜索，能搜到‘C’，则就不会存在人或牛困在死胡同内的情况，故二者可相遇！
个人认为，ls最后一句不对（可证明的）
补充一下，可能人与牛循环运动的路线永远不会相交。
. ........ .
C*******.
.********.
.********.
.********.
.********.
.********.
.********.
.********.
F .........
有同感！ 很可能他们的行进路线是一样的，但他们永远保持一定的距离，而这样的距离永远不会变小变大，他们永远不会相遇！ 只因为他们的方向和速度是一样的！
[编辑] 优化
利用运动周期 大大降低循环次数(code已给出)
易证明:奶牛及约翰各自最终运动路线为一循环.
故:只需模拟时间为二者运动周期最小公倍数之前的所有状态即可.
开数组(以奶牛为例) cow[cowx,cowy,cowface]记录奶牛第一次到达格子[x,y]及朝向状态的时间
当奶牛第二次处于此状态时 显然 奶牛运动周期为cyclecow=time(当前时间)-cow[cowx,cowy,cowface].
可以说明，执行至多5000000步，就可以掐了，如果不掐，差不多就超时了。 标程是模拟就也过不了。。。。
至多250000步，如果这一步以前走过就不走了，掐什么掐 ——祁哥
