【USACO 2.4】The Tamworth Two
2024-10-19 02:26:43
题意:C代表cows,F代表farmer,一开始都向北,每分钟前进1步,如果前方不能走,则这分钟顺时针转90°,问多少步能相遇,或者是否不可能相遇,10*10的地图。
题解:dfs,记录状态,C和F的位置各一维,C和F的方向各一维,所以vis[101][101][5][5]记录是否到过这个状态。
/*
TASK: ttwo
LANG: C++
*/
#include<cstdio>
#include<iostream>
char m[11][11];
int vis[101][101][5][5];
int dx[5]={-1,0,1,0},dy[5]={0,1,0,-1};
int ans;
bool ck(int x,int y){
return x>=0&&x<10&&y>=0&&y<10&&m[x][y]!='*';
}
bool dfs(int fx,int fy,int df,int cx,int cy,int dc){
// printf("f=(%d %d) %d c=(%d %d) %d\n",fx,fy,df,cx,cy,dc);
int ff=fx*10+fy,cc=cx*10+cy;
if(vis[ff][cc][df][dc])return 0;
vis[ff][cc][df][dc]=1;
if(ff==cc)
return 1;
ans++;
int nfx=fx+dx[df],nfy=fy+dy[df],ncx=cx+dx[dc],ncy=cy+dy[dc];
if(!ck(nfx,nfy)){
df=(df+1)%4;
nfx=fx;
nfy=fy;
}
if(!ck(ncx,ncy)){
dc=(dc+1)%4;
ncx=cx;
ncy=cy;
}
if(dfs(nfx,nfy,df,ncx,ncy,dc))return 1;
ans--;
return 0;
}
int main(){
freopen("ttwo.in","r",stdin);
freopen("ttwo.out","w",stdout);
int cx,cy,fx,fy;
for(int i=0;i<10;i++){
scanf("%s",m[i]);
for(int j=0;m[i][j];j++)
if(m[i][j]=='C'){
cx=i;
cy=j;
}else if(m[i][j]=='F'){
fx=i;
fy=j;
}
}
if(dfs(fx,fy,0,cx,cy,0)){
printf("%d\n",ans);
}else{
puts("0");
}
return 0;
}
最新文章
- 使用maven给spring项目打可直接运行的jar包(配置文件内置外置的打法)
- js树形控件—zTree使用总结
- 【leedcode】add-two-numbers
- 解决MD5问题
- 团队作业-第一周-NABCD竞争性需求分析
- day20 FORM补充(随时更新),F/Q操作,model之多对多,django中间件,缓存,信号
- PHP-网页跳转的几种方式
- bzoj2561
- 转载:C#中的多态
- codevs 1269 匈牙利游戏
- 向null地址copy数据和不断改变指针指向
- spring容器IOC原理解析
- JAVA反射机制示例,读取excel数据映射到JAVA对象中
- ubuntu下集群设置静态ip
- 10min系列之二日志可视化进阶
- vim基本命令(转载自网络)
- 解决用try except 捕获assert函数产生的AssertionError异常时,导致断言失败的用例在测试报告中通过的问题
- linux环境下tomcat安装
- windows 10安装jdk8
- android getWidth()和getMeasuredWidth()方法的区别
热门文章
- android 自定义view中findViewById为空的解决办法
- IOS开发基础知识--碎片8
- ios 显示缓存数据库
- shell脚本执行时报";bad interpreter: Text file busy";的解决方法
- Linux如何查找大文件或目录总结
- InstallShield如何做Excel安装与否的检测
- 《java JDK7 学习笔记》之异常处理
- MongoDB学习笔记~大叔框架实体更新支持N层嵌套~递归递归我爱你!
- MySQL性能优化——索引
- 解决undefined reference to `__poll_chk@GLIBC_2.16&#39; 错误