# [USACO2.4] 两只塔姆沃斯牛 The Tamworth Two

[USACO2.4] 两只塔姆沃斯牛 The Tamworth Two

题目描述

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

追击在 10 × 10 10 \times 10 10×10 的平面网格内进行。一个格子可以是:一个障碍物,两头牛(它们总在一起),或者 Farmer John。两头牛和 Farmer John 可以在同一个格子内(当他们相遇时),但是他们都不能进入有障碍的格子。

一个格子可以是:

  • . 空地;
  • * 障碍物;
  • C 两头牛;
  • F Farmer John。

这里有一个地图的例子:

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

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

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

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

读入十行表示地图。每行都只包含 10 个字符,表示的含义和上面所说的相同。保证地图中只有一个 F 和一个 CFC 一开始不会处于同一个格子中。

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

49

提示

翻译来自NOCOW

USACO 2.4
借鉴的代码:主要用了特征值判重
刚刚好每个数值不超过10,即数位上的最大值

#include<cstdio>
bool zt[160005];//10*10*10*10*4*4=160000,开大一点以防万一
char mp[11][11];
int cx,cy,cf,fx,fy,ff,xx[4]={-1,0,1,0},yy[4]={0,1,0,-1},nt,stp;
int main()
{
    for(int i=0;i<10;i++)
    scanf("%s",mp[i]);//读入
    for(int i=0;i<10;i++)
    for(int j=0;j<10;j++)
    {
        if(mp[i][j]=='F')//遇到农夫
        fx=i,fy=j;//设定初始坐标
        if(mp[i][j]=='C')//遇到牛
        cx=i,cy=j;//设定初始坐标
    }
    while(1)
    {
        if(fx==cx&&fy==cy)//相遇了
        {
            printf("%d",stp);//输出步数
            return 0;//退出
        }
        nt=fx+fy*10+cx*100+cy*1000+ff*10000+cf*40000;//生成特征值
        if(zt[nt])//如果出现过了,则无解
        {
            printf("0");
            return 0;
        }
        zt[nt]=1;//保存特征值
        if(fx+xx[ff]<0||fx+xx[ff]>=10||fy+yy[ff]<0||fy+yy[ff]>=10||mp[fx+xx[ff]][fy+yy[ff]]=='*')//判断农夫是否还能向前走
        ff=(ff+1)%4;//如果不行,转向
        else fx=fx+xx[ff],fy=fy+yy[ff];//否则继续向前
        if(cx+xx[cf]<0||cx+xx[cf]>=10||cy+yy[cf]<0||cy+yy[cf]>=10||mp[cx+xx[cf]][cy+yy[cf]]=='*')//判断牛是否还能向前走
        cf=(cf+1)%4;//如果不行,转向
        else cx=cx+xx[cf],cy=cy+yy[cf];//否则继续向前
        stp++;//增加步数
    }
    return 0;
}

lose’s work

#include <iostream>
#include <string>
#include <map>
using namespace std;
int dir[4] = {0,1,2,3};	//分别表示上,右,下,左 顺时针
int go[4][2] = {1,0,0,1,-1,0,0,-1};//与上面相对应
//录入的行数依次递减,即最下方是第一行 
int FX,FY,CX,CY;		//FC的位置 
int FD=0,CD=0;			//方向 
int map1[10][10] = {0}; 	//地图  0:不可行 1:可行 
typedef struct node
{//包含方向才能准确判重 
	int fx,fy,cx,cy;
	int dirF,dirC;
	node(int Fx,int Fy,int Cx,int Cy,int Df,int Dc)
	:fx(Fx),fy(Fy),cx(Cx),cy(Cy),dirF(Df),dirC(Dc){}
	
}point;
struct cmp
{
	bool operator()(struct node const &a, struct node const &b) const //自定义排序
	{
		int sum1 = a.fx+a.fy*10+
		return a.fx<b.fx;
	 } 
};
map<point,bool,cmp> mp;//结合两者来判断是否能抓到牛 
bool judge(int x,int y)
{
	if((x<0)||(x>9)||(y<0)||(y>9))//越界
	return false;
	if(map1[x][y] == 0) 			//不可通 
	return false; 
}
int main()
{
	//读入地图数据 
	for(int i=9;i>=0;i--)
	{ 
		string a;
		cin>>a;
		for(int j=0;j<10;j++)
		{
			if(a[j] == '*') map1[i][j] = 0;
			else if(a[j] == 'F')
			{
				FX = i;FY = j;
				map1[i][j] = 1;
			 } 
			else if(a[j] == 'C')
			{
				CX = i;CY = j;
				map1[i][j] = 1;
			}
			else
			{
				map1[i][j] = 1;
			}
		}
	 }
	int ans=-1; //循环开始时+1,表示当前的时间 
	//进行模拟 
	while(1)
	{
		ans++;
		//移动牛 
		int x,y;//下一步的预定位置
		x = CX+go[CD][0];
		y = CY+go[CD][1]; 
		if(judge(x,y) == false) //转向 
		{system("pause");
			while(judge(x,y) == false)
			{
				CD = (CD+1)%4;
				x = CX+go[CD][0];
				y = CY+go[CD][1]; 
			}
		}
		else
		{
			//直接赋值 
			CX = x;
			CY = y;
		}
		//移动农场主
		x = FX+go[FD][0];
		y = FY+go[FD][1]; 
		if(judge(x,y) == false) //转向 
		{
			while(judge(x,y) == false)
			{
				FD = (FD+1)%4;
				x = FX+go[FD][0];
				y = FY+go[FD][1]; 
			}
		} 
		else
		{
			//直接赋值 
			FX = x;
			FY = y;
		}
		cout<<"      F"<<FX<<"             "<<FY<<"            "<<FD<<endl;
		 cout<<"      C"<<CX<<"             "<<CY<<"           "<<CD<<endl<<endl;
		//判断场面是否重复、是否抓住 
		if(mp.count(point(FX,FY,CX,CY,FD,CD)) == 0) //未重复 
		{cout<<"1111"<<endl;
			mp.insert(map<point,bool>::value_type(point(FX,FY,CX,CY,FD,CD),true)); 
		}
		else
		{cout<<point(FX,FY,CX,CY,FD,CD).dirF<<endl;
			ans = 0;
			break;
		}
		
		if((FX == CX)&&(FY == CY)) break;//成功抓捕 
	 } 
	 cout<<ans;
	return 0;
 } 

map仅对自定义排序所用来比较的元素进行排序,而与结构体中的其他元素无关。而普通map不允许有重复元素,所以尽管其他值不一样,用于排序的值一样就进不去map
还是替换了原来的?
或许可以把状态(坐标、方向)转化成字符串存储在map中查找

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/452707.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

访客到了官网就跳走,概率是官网颜值和体验出了问题。

很多小伙伴反馈官网ip不错&#xff0c;但是pv太少了&#xff0c;停留时间更少&#xff0c;这大概率是网站颜值和体验出问题了。 如果访客到了官网后就跳走&#xff0c;有可能是因为官网的颜值和用户体验出了问题。这种情况可能会导致访客对网站的第一印象不佳&#xff0c;从而选…

【spring】使用阿里Spring Initailiz创建项目

网络原因使用Spring Initailiz会出现超时。 那我们就换成阿里的 先看看spring官网的 网址&#xff1a;https://start.spring.io 使用一下阿里的 网址&#xff1a;https://start.aliyun.com/ 填写信息 都是java开发者&#xff0c;具体信息部介绍了。 选择组件 lombok spri…

OKHttpRetrofit

完成一个get请求 1.导入依赖 implementation("com.squareup.okhttp3:okhttp:3.14.")2.开启viewBinding android.buildFeatures.viewBinding true 3.加网络权限 和 http明文请求允许配置文件 <?xml version"1.0" encoding"utf-8"?> &l…

Kotlin:内联类(inline class)

点击查询内联类中文文档 点击查询内联类英文文档 简介 提醒&#xff1a;内联类仅在 Kotlin 1.3 之后版本可用 有时候&#xff0c;业务逻辑需要围绕某种类型创建包装器。然而&#xff0c;由于额外的堆内存分配问题&#xff0c;它会引入运行时的性能开销。此外&#xff0c;如果…

【嵌入式——QT】标准对话框

【嵌入式——QT】标准对话框 文件对话框颜色对话框字体对话框输入对话框消息框代码示例 文件对话框 QFileDialog 常用静态函数 getOpenFileName&#xff1a;选择打开一个文件&#xff1b;getOpenFileNames&#xff1a;选择打开多个文件&#xff1b;getSaveFileName&#xff1…

如何使用ArcGIS Pro生成带计曲线等高线

等高线作为常见的地图要素经常会被使用到&#xff0c;一般情况下生成的等高线是不带计曲线的&#xff0c;在某些情况下我们需要带计曲线的等高线&#xff0c;这里为大家介绍一下ArcGIS Pro生成带计曲线等高线的方法&#xff0c;希望能对你有所帮助。 数据来源 教程所使用的数…

13、设计模式之模板模式(Template)

一、什么是模板模式 模板模式是一种基于继承实现的设计模式&#xff0c;它是行为型的模式。 主要思想是将定义的算法抽象成一组步骤&#xff0c;在抽象类种定义算法的骨架&#xff0c;把具体的操作留给子类来实现。 通俗地说&#xff0c;模板模式就是将某一行为制定一个框架&…

vue3 实现一个tab切换组件

一. 效果图 二. 代码 文件 WqTab.vue: <template><div ref"wqTabs" class"wq-tab"><template v-for"tab in tabs" :key"tab"><div class"tab-item" :class"{ ac: tabActive tab.key }" c…

LeetCode102题:二叉树的层序遍历(python3)

代码思路&#xff1a;使用队列先进先出的特性&#xff0c;queue[]不为空进入for循环&#xff0c;tmp存储每层的节点&#xff0c;将结果添加至res[]中。 python中使用collections中的双端队列deque()&#xff0c;其popleft()方法可达到O(1)时间复杂度。 class Solution:def lev…

uni-app开发特点和开发流程

uni-app是一个基于Vue.js框架的跨平台应用开发框架&#xff0c;通过一套代码可以同时运行在多个平台上&#xff0c;包括iOS、Android、H5等。它采用了基于流布局的页面渲染机制&#xff0c;可以自动适配不同平台的屏幕尺寸和分辨率。uniapp官网&#xff1a;https://uniapp.dclo…

概率与常见的概率分布

概率是数据分析、机器学习中最基础的知识。也是在生活中最实用的一门学科&#xff0c;学了很多大道理不一定能过好一生&#xff0c;学好概率则有一定概率会变得更好。为大概率坚持&#xff0c;为小概率备份。 概率与分布 要想了解概率&#xff0c;首先得搞清楚概率和概率分布的…

2024蓝桥杯每日一题(区间合并)

一、第一题&#xff1a;挤牛奶 解题思路&#xff1a;区间合并 区间合并模板题 【Python程序代码】 n int(input()) a [] for i in range(n):l,r map(int,input().split())a.append([l,r]) def cmp(x):return x[0],x[1] a.sort(keycmp) res1,res20,0 st,ed a[0][0…

SQLiteC/C++接口详细介绍之sqlite3类(五)

快速跳转文章列表&#xff1a;SQLite—系列文章目录 上一篇&#xff1a;SQLiteC/C接口详细介绍之sqlite3类&#xff08;四&#xff09; 下一篇&#xff1a;SQLiteC/C接口详细介绍之sqlite3类&#xff08;六&#xff09;&#xff08;未发表&#xff09; 14.sqlite3_busy_handle…

猫咪挑食不吃猫粮是为什么?适口性好、普口性价的主食冻干推荐

现在咱养猫人个个吧自家的小猫咪当成宝贝宠着&#xff0c;宠着宠着一些坏习惯就出来。 然而&#xff0c;这种宠爱有时也会导致猫咪养成挑食的不良习惯。那么&#xff0c;当猫咪拒绝吃猫粮时&#xff0c;我们应该如何应对呢&#xff1f;今天跟大家一起来分析分析猫咪挑食不吃猫…

Claude3相较于GPT4有哪些优点?

Claude 最实在的一点是即使是普通用户&#xff0c;也能用到上传文件、上传图片这些功能&#xff08;只是用的模型比付费版性能差一些&#xff0c;对普通用户开放的是 Sonnet 版本&#xff0c;付费用户是 Opus 版本&#xff09;。 但是 ChatGPT 就不行&#xff0c;免费的 GPT-3…

唯众物联网+地理科学交付云南师范大学地理学部教学实验室项目

近日&#xff0c;云南师范大学地理学部教学实验室建设项目顺利交付。该项目的成功落地&#xff0c;标志着物联网技术与地理科学教育的深度融合&#xff0c;为云南师范大学的地理教学提供了全新的教学平台与资源。该项目以物联网技术为核心&#xff0c;结合地理科学的特点&#…

UI 学习 二 可访问性 模式

一 颜色对比 颜色和对比度可以用来帮助用户看到和理解应用程序的内容&#xff0c;与正确的元素交互&#xff0c;并理解操作。 颜色可以帮助传达情绪、语气和关键信息。可以选择主色、辅助色和强调色来支持可用性。元素之间足够的颜色对比可以帮助低视力的用户看到和使用你的应…

Qt QDateTime类使用

一.Qt datetime 介绍 Qt中的QDateTime类是用于处理日期和时间的组合的类&#xff0c;它提供了丰富的功能来操作和格式化日期时间数据。以下是其主要特点和用法&#xff1a; 构造函数&#xff1a;QDateTime可以通过组合QDate&#xff08;日期&#xff09;和QTime&#xff08;时…

微信小程序之vue按钮切换内容变化

效果图如下&#xff1b; 上代码 <template><view class"content"><view class"searchDiv"><view class"paytab"><view class"buttab" v-for"(t,index) in tabList" :key"index" clic…

基于java+springboot开发的计算机毕业设计网文论坛管理系统设计与实现【附源码】

基于javaspringboot开发的计算机毕业设计网文论坛管理系统设计与实现【附源码】 &#x1f345; 作者主页 央顺技术团队 &#x1f345; 欢迎点赞 &#x1f44d; 收藏 ⭐留言 &#x1f4dd; &#x1f345; 文末获取源码联系方式 &#x1f4dd; &#x1f345; 查看下方微信号获取联…