题意: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;
}

  

最新文章

  1. 使用maven给spring项目打可直接运行的jar包(配置文件内置外置的打法)
  2. js树形控件—zTree使用总结
  3. 【leedcode】add-two-numbers
  4. 解决MD5问题
  5. 团队作业-第一周-NABCD竞争性需求分析
  6. day20 FORM补充(随时更新),F/Q操作,model之多对多,django中间件,缓存,信号
  7. PHP-网页跳转的几种方式
  8. bzoj2561
  9. 转载:C#中的多态
  10. codevs 1269 匈牙利游戏
  11. 向null地址copy数据和不断改变指针指向
  12. spring容器IOC原理解析
  13. JAVA反射机制示例,读取excel数据映射到JAVA对象中
  14. ubuntu下集群设置静态ip
  15. 10min系列之二日志可视化进阶
  16. vim基本命令(转载自网络)
  17. 解决用try except 捕获assert函数产生的AssertionError异常时,导致断言失败的用例在测试报告中通过的问题
  18. linux环境下tomcat安装
  19. windows 10安装jdk8
  20. android getWidth()和getMeasuredWidth()方法的区别

热门文章

  1. android 自定义view中findViewById为空的解决办法
  2. IOS开发基础知识--碎片8
  3. ios 显示缓存数据库
  4. shell脚本执行时报&quot;bad interpreter: Text file busy&quot;的解决方法
  5. Linux如何查找大文件或目录总结
  6. InstallShield如何做Excel安装与否的检测
  7. 《java JDK7 学习笔记》之异常处理
  8. MongoDB学习笔记~大叔框架实体更新支持N层嵌套~递归递归我爱你!
  9. MySQL性能优化——索引
  10. 解决undefined reference to `__poll_chk@GLIBC_2.16&#39; 错误