USACO2.4 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。
输入输出样例
*...*.....
......*...
...*...*..
..........
...*.F....
*.....*...
...*......
..C......*
...*.*....
.*.*......
49
说明
翻译来自NOCOW
USACO 2.4
比较好玩,while里模拟,6维数组判重
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define debug(x) cout<<#x<<'='<<x<<' '
using namespace std;
typedef long long ll;
const int N=;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int a[N][N],fx,fy,fd=,cx,cy,cd=,ans=,vis[N][N][][N][N][];
char s[N];
inline bool check(int x,int y){
if(x>=&&x<=&&y>=&&y<=&&!a[x][y]) return ;
else return ;
}
inline void walk(int &x,int &y,int &d){
int tx=x,ty=y;
if(d==) tx--;
else if(d==) ty++;
else if(d==) tx++;
else if(d==) ty--;
if(check(tx,ty)){x=tx;y=ty;}
else d=(d+)%;
}
int main(){
for(int i=;i<=;i++){
scanf("%s",s+);
for(int j=;j<=;j++){
if(s[j]=='*') a[i][j]=;
if(s[j]=='F') {fx=i;fy=j;}
if(s[j]=='C') {cx=i;cy=j;}
}
}
while(true){
//printf("%d %d %d %d\n",fx,fy,cx,cy);
if(fx==cx&&fy==cy){printf("%d",ans);return ;}
if(vis[fx][fy][fd][cx][cy][cd]) break;
vis[fx][fy][fd][cx][cy][cd]=;
walk(fx,fy,fd);
walk(cx,cy,cd);
ans++;
}
putchar('');
}
最新文章
- Java web servlet 拦截器 以登陆为例子
- linux-----------shell的基础命令
- (function($){}) 和$(function(){}) 和$(function($){}) 区别
- 拖拽改变div的大小
- [转]JavaScript实现 页面滚动图片加载
- Linux常用命令_(系统管理)
- 【风马一族_xml】Schema--- xml的约束技术
- 《C和指针》 读书笔记 -- 第11章 动态内存分配
- APUE(3)——文件I/O
- Go 解析JSON
- 用js捕捉鼠标连续点击三次事件怎么实现啊
- [置顶] Codeforces 70D 动态凸包 (极角排序 or 水平序)
- iOS搜索框UISearchBar
- JavaScript+canvas 绘制多边形
- codeforces 883M. Quadcopter Competition 思路
- python文件和文件夹訪问File and Directory Access
- vue-cli 2.92版本 server
- spring-cloud-config-server——Environment Repository
- python之操作系统介绍,进程的创建
- AutoMapper在MVC中的运用03-字典集合、枚举映射,自定义解析器
热门文章
- uct框架数据库sql文件导入错误之 sql_mode
- 使用block进行界面之间的反向传值
- python征程2.0(python基础)
- link与@import的区别
- [deviceone开发]-利用do_ListView模拟单选功能
- <;td>;<;/td>;标签的border 样式在浏览器中显示不出来
- jQuery静态方法parseXML使用和源码分析
- OC NSFileHandle(文件内容操作)
- CLR垃圾回收的设计
- SQL SERVER 2014 下IF EXITS 居然引起执行计划变更的案例分享