【USACO 2.4】The Tamworth Two
The 2.4 two USACO
2023-09-11 14:19:25 时间
题意: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; }
相关文章
- Timeout expired. The timeout period elapsed prior to completion of the operation or the server is not responding.
- eplise中运行提示 A fatal error has been detected by the java runtime environment
- How I can obtain the collation of a specific table in a database?
- Being Agile vs. doing Agile: What's the difference?
- Cannot import the keyfile 'blah.pfx' - error 'The keyfile may be password protected'
- SHA1 VS RSA: what's the difference between them?
- What are the differences between Flyweight and Object Pool patterns?
- The revocation function was unable to check revocation for the certificate
- The remote end hung up unexpectedly while git cloning
- 【CF802L】Send the Fool Further! (hard) 高斯消元
- the mail of you!
- The last access date is not changed even after reading the file on Windows 7
- 在执行脚本./scripts/get_maintainer.pl时报错"Can't locate File/Find.pm in @INC (you may need to install the File::Find module) (@INC contains:"如何处理?
- git:RPC failed; HTTP 413 curl 22 The requested URL returned error: 413 Reques t Entity Too Larg
- Git上传出现:The requested URL returned error: 403解决办法
- The connection to adb is down, and a severe error has occured.问题解决
- Tomcat 8 Invalid character found in the request target. The valid characters are defined in RFC 3986
- MYSQL导入csv类型的数据出现The MySQL server is running with the --secure-file-priv option
- 启动 Eclipse 弹出“Failed to load the JNI shared library jvm.dll”错误的解决方法!
- Mysql_解决The total number of locks exceeds the lock table size错误
- Weblogic发布小问题——The root element weblogic-web-app is missing in the descriptor file
- php curl Problem with the SSL CA cert (path access rights)
- HDU 4462Scaring the Birds(枚举所有状态)
- HDU 1597 find the nth digit
- The incident LOST_EVENTS occured on the master. Message: error writing to the binary log, Error_code
- The OAuth 2.0 Authorization Framework-摘自https://tools.ietf.org/html/rfc6749
- Installing Windows Identity Foundation on Windows 8 - The Certificate for the signer of the message is invalid or not found.
- [LeetCode] 287. Find the Duplicate Number 寻找重复数
- Understanding AMQP, the protocol used by RabbitMQ--reference
- 【安卓-疑难杂症】:你的主机中的软件中止了一个已建立的连接 and The application could not be installed: INSTALL_FAILED_USER_RESTRI
- gridControl-The BindingSource.AddingNew event does not fire until I begin typing into the new row
- 【学习笔记】成功解决:(字体问题)Package fontspec Error: The font “STXingkai“ cannot be found. makecover
- 《Keep your Eyes on the Lane:Real-time Attention-guided Lane Detection》
- 圣诞特辑-解决idea新建报错The required Java version 11 is not supported by the project SDK 1.8.
- PHP配置Configure报错:Please reinstall the libzip distribution
- java.lang.IllegalArgumentException: Invalid character found in the request target. The valid characters are defined in RFC 7230 and RFC 3986