博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
HDU 4740 The Donkey of Gui Zhou
阅读量:4938 次
发布时间:2019-06-11

本文共 4406 字,大约阅读时间需要 14 分钟。

The Donkey of Gui Zhou

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on 
HDU. Original ID: 
64-bit integer IO format: %I64d      Java class name: Main
 
There was no donkey in the province of Gui Zhou, China. A trouble maker shipped one and put it in the forest which could be considered as an N×N grid. The coordinates of the up-left cell is (0,0) , the down-right cell is (N-1,N-1) and the cell below the up-left cell is (1,0)..... A 4×4 grid is shown below:
The donkey lived happily until it saw a tiger far away. The donkey had never seen a tiger ,and the tiger had never seen a donkey. Both of them were frightened and wanted to escape from each other. So they started running fast. Because they were scared, they were running in a way that didn't make any sense. Each step they moved to the next cell in their running direction, but they couldn't get out of the forest. And because they both wanted to go to new places, the donkey would never stepped into a cell which had already been visited by itself, and the tiger acted the same way. Both the donkey and the tiger ran in a random direction at the beginning and they always had the same speed. They would not change their directions until they couldn't run straight ahead any more. If they couldn't go ahead any more ,they changed their directions immediately. When changing direction, the donkey always turned right and the tiger always turned left. If they made a turn and still couldn't go ahead, they would stop running and stayed where they were, without trying to make another turn. Now given their starting positions and directions, please count whether they would meet in a cell.
 

Input

There are several test cases.
In each test case:
First line is an integer N, meaning that the forest is a N×N grid.
The second line contains three integers R, C and D, meaning that the donkey is in the cell (R,C) when they started running, and it's original direction is D. D can be 0, 1, 2 or 3. 0 means east, 1 means south , 2 means west, and 3 means north.
The third line has the same format and meaning as the second line, but it is for the tiger.
The input ends with N = 0. ( 2 <= N <= 1000, 0 <= R, C < N)
 

Output

For each test case, if the donkey and the tiger would meet in a cell, print the coordinate of the cell where they meet first time. If they would never meet, print -1 instead.
 

Sample Input

20 0 00 1 240 1 03 2 00

Sample Output

-11 3

Source

 
解题:模拟什么的最难搞了
1 #include 
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 #include
9 #include
10 #include
11 #include
12 #include
13 #define LL long long14 #define INF 0x3f3f3f3f15 #define pii pair
16 using namespace std;17 const int maxn = 1005;18 bool vd[maxn][maxn],vt[maxn][maxn];19 int n,dx,dy,dr,tx,ty,tr;20 bool dstop,tstop;21 const int dir[4][2] = { 0,1,1,0,0,-1,-1,0};22 bool ismeet() {23 return (tx == dx && ty == dy);24 }25 bool isIn(int x,int y) {26 return (x >= 0 && y >= 0 && x < n && y < n);27 }28 bool go() {29 dstop = false;30 tstop = false;31 while(true) {32 int nx = dx + dir[dr][0];33 int ny = dy + dir[dr][1];34 if(!dstop&&isIn(nx,ny) && !vd[nx][ny]) {35 dx = nx;36 dy = ny;37 vd[dx][dy] = true;38 } else if(!dstop) {39 int ddr = (dr + 1)%4;40 nx = dx + dir[ddr][0];41 ny = dy + dir[ddr][1];42 if(isIn(nx,ny) && !vd[nx][ny]) {43 dx = nx;44 dy = ny;45 dr = ddr;46 vd[dx][dy] = true;47 } else dstop = true;48 }49 50 nx = tx + dir[tr][0];51 ny = ty + dir[tr][1];52 if(!tstop && isIn(nx,ny) && !vt[nx][ny]) {53 tx = nx;54 ty = ny;55 vt[tx][ty] = true;56 } else if(!tstop) {57 int ttr = (tr + 3)%4;58 nx = tx + dir[ttr][0];59 ny = ty + dir[ttr][1];60 if(isIn(nx,ny) && !vt[nx][ny]) {61 tx = nx;62 ty = ny;63 tr = ttr;64 vt[tx][ty] = true;65 } else tstop = true;66 }67 if(ismeet()) return true;68 if(tstop && dstop) break;69 }70 return false;71 }72 int main() {73 while(scanf("%d",&n),n) {74 scanf("%d %d %d",&dx,&dy,&dr);75 scanf("%d %d %d",&tx,&ty,&tr);76 memset(vd,false,sizeof(vd));77 memset(vt,false,sizeof(vt));78 vd[dx][dy] = true;79 vt[tx][ty] = true;80 if(tx == dx && dy == ty) {81 printf("%d %d\n",tx,ty);82 continue;83 }84 if(go()) printf("%d %d\n",tx,ty);85 else puts("-1");86 }87 return 0;88 }
View Code

 

转载于:https://www.cnblogs.com/crackpotisback/p/4106095.html

你可能感兴趣的文章
评论:人才流失强力折射出现实畸形人才观
查看>>
git服务器gitlab之搭建和使用--灰常好的git服务器【转】
查看>>
基于机器学习的web异常检测——基于HMM的状态序列建模,将原始数据转化为状态机表示,然后求解概率判断异常与否...
查看>>
分享一种需求评审的方案
查看>>
虚拟运营商10月或大面积放号 哭穷背后仍有赢家
查看>>
Server2016开发环境配置
查看>>
分布式光伏发电建设中的逆变器及其选型
查看>>
增强网络安全防御 推动物联网走向应用
查看>>
UML中关联,组合与聚合等关系的辨析
查看>>
《大数据管理概论》一3.2 大数据存储与管理方法
查看>>
PowerBuilder开发简单计算器
查看>>
怎样使用linux的iptables工具进行网络共享
查看>>
《HTML5与CSS3实战指南》——导读
查看>>
RHEL6下安装oracle 10g(一)
查看>>
Kconfig的格式
查看>>
关于Cursor的moveToFirst和moveToNext的意义
查看>>
个人--工资划分5份
查看>>
有关文件下载的文件名
查看>>
史上最详细的wamp配置虚拟域名步骤
查看>>
oracle 授权
查看>>