luogu P1518 两只塔姆沃斯牛 The Tamworth Two
发布日期:2022-02-22 18:04:16 浏览次数:8 分类:技术文章

本文共 2265 字,大约阅读时间需要 7 分钟。

luogu P1518 两只塔姆沃斯牛 The Tamworth Two

题目描述

两只牛逃跑到了森林里。农夫John开始用他的专家技术追捕这两头牛。你的任务是模拟他们的行为(牛和John)。

追击在10x10的平面网格内进行。一个格子可以是:

一个障碍物, 两头牛(它们总在一起), 或者 农民John. 两头牛和农民John可以在同一个格子内(当他们相遇时),但是他们都不能进入有障碍的格子。

一个格子可以是:

. 空地

* 障碍物

C 两头牛

F 农民John

这里有一个地图的例子:

*...*...........*......*...*...............*.F....*.....*......*........C......*...*.*.....*.*......

牛在地图里以固定的方式游荡。每分钟,它们可以向前移动或是转弯。如果前方无障碍(地图边沿也是障碍),它们会按照原来的方向前进一步。否则它们会用这一分钟顺时针转90度。 同时,它们不会离开地图。

农民John深知牛的移动方法,他也这么移动。

每次(每分钟)农民John和两头牛的移动是同时的。如果他们在移动的时候穿过对方,但是没有在同一格相遇,我们不认为他们相遇了。当他们在某分钟末在某格子相遇,那么追捕结束。

读入十行表示农夫John,两头牛和所有障碍的位置的地图。每行都只包含10个字符,表示的含义和上面所说的相同,你可以确定地图中只有一个'F'和一个'C'.'F'和'C'一开始不会处于同一个格子中。

计算农夫John需要多少分钟来抓住他的牛,假设牛和农夫John一开始的行动方向都是正北(即上)。 如果John和牛永远不会相遇,输出0。

输入输出格式

输入格式:

每行10个字符,表示如上文描述的地图。

输出格式:

输出一个数字,表示John需要多少时间才能抓住牛们。如果John无法抓住牛,则输出0。

输入输出样例

输入样例#1:

*...*...........*......*...*...............*.F....*.....*......*........C......*...*.*.....*.*......

输出样例#1:

49

这个破题乍一看应该是模拟,但是模拟似乎无从下手

但是发现地图只有10*10

方向只有4个,所以可以用到(搜索?)的思想,可以设状态来判无解的情况

所以我们设\(f[\varphi][k1][\theta][k2]\)为第一个点为\(\varphi\)方向为\(k1\)第二个点为\(\theta\)方向为\(k2\)的状态

然后就可以大力循环(递归?)

点的结构体:

bool inmp(int x,int y){    return 1<=x&&x<=10&&1<=y&&y<=10&&mp[x][y]!='*';}struct p{    int x,y,k;    void turn(){k=(k+1)%4;}    friend p& operator ++ (p &a){        if(!inmp(a.x+dx[a.k],a.y+dy[a.k]))a.turn();        else {a.x+=dx[a.k],a.y+=dy[a.k];}        return a;    }    friend bool operator == (const p &a,const p &b){        return a.x==b.x&&a.y==b.y;    }}a,b,c;

为了方便直接用++当做走一步

然后就可以循环/递归枚举每次走的情况

void dfs(p a,p b,int step){    if(f[a.x][a.y][a.k][b.x][b.y][b.k]){cout<<0<

并没有什么用的递归QWQ

完整代码:

#include
#include
using namespace std;char mp[15][15];const int dx[]={-1,0,1,0},dy[]={0,1,0,-1};int f[11][11][4][11][11][4];bool inmp(int x,int y){ return 1<=x&&x<=10&&1<=y&&y<=10&&mp[x][y]!='*';}struct p{ int x,y,k; void turn(){k=(k+1)%4;} friend p& operator ++ (p &a){ if(!inmp(a.x+dx[a.k],a.y+dy[a.k]))a.turn(); else {a.x+=dx[a.k],a.y+=dy[a.k];} return a; } friend bool operator == (const p &a,const p &b){ return a.x==b.x&&a.y==b.y; }}a,b,c;void dfs(p a,p b,int step){ if(f[a.x][a.y][a.k][b.x][b.y][b.k]){cout<<0<

转载于:https://www.cnblogs.com/eric-walker/p/9620587.html

转载地址:https://blog.csdn.net/dengxingrao0615/article/details/102231368 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:牛客网NOIP赛前集训营-提高组(第四场)B区间
下一篇:noip提高组模拟赛(QBXT)T2

发表评论

最新留言

做的很好,不错不错
[***.243.131.199]2024年03月01日 03时20分30秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

lin通讯从节点同步间隔场_LIN模块介绍 2019-04-21
mysql注入提取邮件_Mysql提取数据每日自动邮件通知 2019-04-21
mysql 列权限_mysql 权限相关 2019-04-21
手机端 vue+vant datetime支持时分秒_vueCli4+vant+router+vuex+移动端适配 2019-04-21
kafka消费者直接存在mysql中_【Canal】利用canal实现mysql实时增量备份并对接kafka 2019-04-21
python中readlines()函数_python中读取文件函数read()、readline()、readlines()的区别 2019-04-21
python入门之基础语法第四关输入输出答案_Python基本语法入门,基础 2019-04-21
mysql在存储过程仍_mysql存储过程 2019-04-21
失败的人生图片_早安励志经典语录精辟的一句话人生感悟 2019-04-21
如何设画面大小_如何设计旅游类项目?分享3种设计思路 2019-04-21
开启web_2021秋招四大网申时间、网申地址汇总(持续更新),德勤、安永、普华永道已开启!... 2019-04-21
从右边开始放_停路边,被人恶意放钉子,爆胎,报警无果,要我找监控 2019-04-21
读写测试_UFS 3.0读写测试数据曝光:秒杀UFS 2.1和eMMC 2019-04-21
注册小程序要多少钱_开发一个微信小程序商城要多少钱? 2019-04-21
mysql 实现id自增序列_MySQL分表自增ID解决方案 2019-04-21
反距离加权插值法例题_空间插值算法-反距离加权法 2019-04-21
oracle如何写循环日期自增_Oracle动态创建时间分区,以及Oracle12c中快速创建自增列... 2019-04-21
手机gps信息提取并储存到本地_通信人的实用技巧,如何在日常拍的照片里提取GPS位置信息... 2019-04-21
linux 怎么找到web日志文件,Linux 检查websphere 的application的日志文件 2019-04-21
window自动上传linux,利用putty证书实现linux和window文件自动同步 2019-04-21