BIO '98 - Richard Forster
A pair of cows is loose somewhere in the forest. Farmer John is lending his expertise to their capture. Your task is to model their behavior.
The chase takes place on a 10 by 10 planar grid. Squares can be empty or they can contain:
- an obstacle,
- the cows (who always travel together), or
- Farmer John.
The cows and Farmer John can occupy the same square (when they `meet') but neither the cows nor Farmer John can share a square with an obstacle.
Each square is
|
Here is a sample grid:
*...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*...... |
The cows wander around the grid in a fixed way. Each minute, they either move forward or rotate. Normally, they move one square in the direction they are facing. If there is an obstacle in the way or they would leave the board by walking `forward', then they spend the entire minute rotating 90 degrees clockwise.
Farmer John, wise in the ways of cows, moves in exactly the same way.
The farmer and the cows can be considered to move simultaneously during each minute. If the farmer and the cows pass each other while moving, they are not considered to have met. The chase ends when Farmer John and the cows occupy the same square at the end of a minute.
Read a ten-line grid that represents the initial state of the cows, Farmer John, and obstacles. Each of the ten lines contains exactly ten characters using the coding above. There is guaranteed to be only one farmer and one pair of cows. The cows and Farmer John will not initially be on the same square.
Calculate the number of minutes until the cows and Farmer John meet. Assume both the cows and farmer begin the simulation facing in the `north' direction. Print 0 if they will never meet.
PROGRAM NAME: ttwo
INPUT FORMAT
Lines 1-10: | Ten lines of ten characters each, as explained above |
SAMPLE INPUT (file ttwo.in)
*...*..... ......*... ...*...*.. .......... ...*.F.... *.....*... ...*...... ..C......* ...*.*.... .*.*......
OUTPUT FORMAT
A single line with the integer number of minutes until Farmer John and the cows meet. Print 0 if they will never meet.
SAMPLE OUTPUT (file ttwo.out)
49
题意:
给出一个 10 X 10 的地图,给出每个点的状态,F 代表 famer 的位置,C 代表 cow 的位置,* 代表障碍物,. 代表通道。F 和C 同时运动,输出他们相遇时候的步数。每次他们只会朝着一个方向走,一开始朝南,后碰到障碍物或者边界则换方向,方向沿顺时针转 90°。若无法相遇则输出 0 。转方向过程也算一个步数。
思路:
技巧模拟。用 dir = (dir + 1 ) % 4 来模拟旋转的情况,旋转的时候也算一个时间,故不用更新该点的位置,只是更新方向。每个点都有4个方向的状态,那么一共有4 * 10 * 10 = 400种状态,两个点那么最多也只会走 400 * 400 = 160000 次。故循环完160000还未找到的话,永远也就不会再找到了。
AC:
/* TASK:ttwo LANG:C++ ID:sum-g1 */ #include <cstdio> #define MAX 160000 using namespace std; char Map[15][15]; int fx,fy,cx,cy,df,dc,ans; int dir[4][2] = {-1,0,0,1,1,0,0,-1}; void next() { fx += dir[df][0]; fy += dir[df][1]; if(fx < 1 || fx > 10 || fy < 1 || fy > 10 || Map[fx][fy] == '*') { fx -= dir[df][0]; fy -= dir[df][1]; df = (df + 1) % 4; } cx += dir[dc][0]; cy += dir[dc][1]; if(cx < 1 || cx > 10 || cy < 1 || cy > 10 || Map[cx][cy] == '*') { cx -= dir[dc][0]; cy -= dir[dc][1]; dc = (dc + 1) % 4; } } void solve() { df = dc = 0; while(ans <= MAX) { if(fx == cx && fy == cy) return; next(); ans++; } if(ans == MAX + 1) ans = 0; } int main() { freopen("ttwo.in","r",stdin); freopen("ttwo.out","w",stdout); for (int i = 1; i <= 10; ++i) for (int j = 1; j <= 10; ++j) { scanf(" %c",&Map[i][j]); if (Map[i][j] == 'F') { fx = i; fy = j; } if (Map[i][j] == 'C') { cx = i; cy = j; } } solve(); printf("%d\n",ans); return 0; }
相关推荐
[USACO2.4] 两只塔姆沃斯牛 The Tamworth Two是一个暴力枚举问题,给定一个 10 × 10 的图,其中有的格子是障碍物,有一个农夫在追一个牛。我们需要计算农夫多长时间可以追上牛。如果追不上,输出 0。 这个问题可以...
Tamworth Two (存储历史状态,用于判断是否存在循环) P1249 最大乘积 (贪心, 动态规划, 01背包, 大数乘法) P1045 麦森数 (大数乘法(保留多少位), 快速幂的思想) P1177 快速排序 (要多看看排序算法..,多总结...!!!...
在英国Tamworth的一所名为Relax Kids的学校,一位教师Rosie Dutton设计了一个创新的课堂活动,旨在向学生们展示欺凌行为可能带来的潜在伤害。这个活动不仅仅停留在理论知识的传授上,更通过实物操作,让学生们亲眼...
轴类零件加工工艺设计.zip
资源内项目源码是来自个人的毕业设计,代码都测试ok,包含源码、数据集、可视化页面和部署说明,可产生核心指标曲线图、混淆矩阵、F1分数曲线、精确率-召回率曲线、验证集预测结果、标签分布图。都是运行成功后才上传资源,毕设答辩评审绝对信服的保底85分以上,放心下载使用,拿来就能用。包含源码、数据集、可视化页面和部署说明一站式服务,拿来就能用的绝对好资源!!! 项目备注 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、大作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.txt文件,仅供学习参考, 切勿用于商业用途。
seaborn基本绘图人力资源数据集
移动机器人(sw三维)
自制html网页源代码查看器
3吨叉车的液压系统设计().zip
1_实验三 扰码、卷积编码及交织.ppt
北京交通大学软件学院自命题科目考试大纲.pdf
雅鲁藏布江流域 shp矢量数据 (范围+DEM).zip
基于RUST的数据结构代码示例,栈、队列、图等
NIFD:2024Q1房地产金融报告
详细介绍及样例数据:https://blog.csdn.net/li514006030/article/details/146916652
【工业机器视觉定位软件Vision-Detect】基于C#的WPF与Halcon开发的工业机器视觉定位软件(整套源码),开箱即用 有用户登录,图片加载,模板创建,通讯工具,抓边抓圆,良率统计,LOG日志,异常管理,九点标定和流程加载保存等模块,功能不是很完善,适合初学者参考学习。 资源介绍请查阅:https://blog.csdn.net/m0_37302966/article/details/146912206 更多视觉框架资源:https://blog.csdn.net/m0_37302966/article/details/146583453
内容概要:本文档详细介绍了Java虚拟机(JVM)的相关知识点,涵盖Java内存模型、垃圾回收机制及算法、垃圾收集器、内存分配策略、虚拟机类加载机制和JVM调优等内容。首先阐述了Java代码的编译和运行过程,以及JVM的基本组成部分及其运行流程。接着深入探讨了JVM的各个运行时数据区,如程序计数器、Java虚拟机栈、本地方法栈、Java堆、方法区等的作用和特点。随后,文档详细解析了垃圾回收机制,包括GC的概念、工作原理、优点和缺点,并介绍了几种常见的垃圾回收算法。此外,文档还讲解了JVM的分代收集策略,新生代和老年代的区别,以及不同垃圾收集器的工作方式。最后,文档介绍了类加载机制、JVM调优的方法和工具,以及常用的JVM调优参数。 适合人群:具备一定Java编程基础的研发人员,尤其是希望深入了解JVM内部机制、优化程序性能的技术人员。 使用场景及目标:①帮助开发人员理解Java代码的编译和执行过程;②掌握JVM内存管理机制,包括内存分配、垃圾回收等;③熟悉类加载机制,了解类加载器的工作原理;④学会使用JVM调优工具,掌握常用调优参数,提升应用程序性能。 其他说明:本文档内容详尽,适合用作面试准备材料和技术学习资料,有助于提高开发人员对JVM的理解和应用能力。
Android项目原生java语言课程设计,包含LW+ppt
戴德梁行&中国房地产协会:2021亚洲房地产投资信托基金研究报告
Android项目原生java语言课程设计,包含LW+ppt