首页 > ACM题库 > HDU-杭电 > hdu 4452-running rabbits-模拟-[解题报告]hoj
2015
07-16

hdu 4452-running rabbits-模拟-[解题报告]hoj

题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=4452

 

题目描述:

Running Rabbits

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 388    Accepted Submission(s): 284

Problem Description
      Rabbit Tom and rabbit Jerry are running in a field. The field is an N×N grid. Tom starts from the up-left cell and Jerry starts from the down-right cell. The coordinate of the up-left cell is (1,1) and the coordinate of the
down-right cell is (N,N)。A 4×4 field and some coordinates of its cells are shown below:


      The rabbits can run in four directions (north, south, west and east) and they run at certain speed measured by cells per hour. The rabbits can’t get outside of the field. If a rabbit can’t run ahead any more, it will turn around and keep running. For
example, in a 5×5 grid, if a rabbit is heading west with a speed of 3 cells per hour, and it is in the (3, 2) cell now, then one hour later it will get to cell (3,3) and keep heading east. For example again, if a rabbit is in the (1,3) cell and it is heading
north by speed 2,then a hour latter it will get to (3,3). The rabbits start running at 0 o’clock. If two rabbits meet in the same cell at k o’clock sharp( k can be any positive integer ), Tom will change his direction into Jerry’s direction, and Jerry also
will change his direction into Tom’s original direction. This direction changing is before the judging of whether they should turn around.
      The rabbits will turn left every certain hours. For example, if Tom turns left every 2 hours, then he will turn left at 2 o’clock , 4 o’clock, 6 o’clock..etc. But if a rabbit is just about to turn left when two rabbit meet, he will forget to turn this
time. Given the initial speed and directions of the two rabbits, you should figure out where are they after some time.
 

 

Input
      There are several test cases.
      For each test case:
      The first line is an integer N, meaning that the field is an N×N grid( 2≤N≤20).
      The second line describes the situation of Tom. It is in format "c s t"。c is a letter indicating the initial running direction of Tom, and it can be ‘W’,'E’,'N’ or ‘S’ standing for west, east, north or south. s is Tom’s speed( 1≤s<N). t means that Tom
should turn left every t hours( 1≤ t ≤1000).
      The third line is about Jerry and it’s in the same format as the second line.
      The last line is an integer K meaning that you should calculate the position of Tom and Jerry at K o’clock( 1 ≤ K ≤ 200).
      The input ends with N = 0.
 

 

Output
      For each test case, print Tom’s position at K o’clock in a line, and then print Jerry’s position in another line. The position is described by cell coordinate.
 

 

Sample Input
4 E 1 1 W 1 1 2 4 E 1 1 W 2 1 5 4 E 2 2 W 3 1 5 0
 

 

Sample Output
2 2 3 3 2 1 2 4 3 1 4 1

 

 

 

 

 

题意:说有两个对象初始在左上角和右下角,以固定的速度运动,有三条规则运动。

           1、撞墙会反弹方向

           2、相撞会交换各自的运动方向

           3、每隔固定时间会向左变换一次方向

           另外,相撞的时候如果正好要变换一次坐方向,那么变换左方向这个动作将忽略。

 

题解:模拟,按照题意模拟就行了,注意各个规则的优先次序,2规则会将同时发生的3规则抹掉,并且注意两个对象的初始位置,接下来照着模拟就行了。

 

代码:

/*
Running Rabbits
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
using namespace std;
typedef struct Rabbit
{
	char Direc[2+5];
	int Speed;
	int hour;
	int row;
	int col;
	Rabbit()
	{
		memset(Direc,'\0',sizeof(Direc));
		Speed=0;
		hour=0;
		row=0;
		col=0;
	}
}Rabbit,*RabbitLink;
Rabbit Tom,Jerry;
int N=0;//N*N Maze
int K=0;//time process
/*move the cell by its speed and direction*/
int MoveAhead(Rabbit &Cell)
{
	switch(Cell.Direc[0])
	{
		case 'N':
		Cell.row-=Cell.Speed;
		break;
		case 'E':
		Cell.col+=Cell.Speed;
		break;
		case 'S':
		Cell.row+=Cell.Speed;
		break;
		case 'W':
		Cell.col-=Cell.Speed;
		break;
	}
	return(0);
}
/*judge the row and col whether overflow*/
bool IsWall(Rabbit &Cell)
{
	if(Cell.row<1||Cell.row>N||Cell.col<1||Cell.col>N)
	{
		return(true);
	}
	else
	{
		return(false);
	}
}
/*turnaround the cell to the contrary direction*/
int TurnAround(Rabbit &Cell)
{
	if(Cell.row<1)//North overflow
	{
		Cell.Direc[0]='S';
		Cell.row=fabs(Cell.row-1)+1;
	}
	else if(Cell.row>N)//South overflow
	{
		Cell.Direc[0]='N';
		Cell.row=N-fabs(Cell.row-N);
	}
	if(Cell.col<1)//West overflow
	{
		Cell.Direc[0]='E';
		Cell.col=fabs(Cell.col-1)+1;
	}
	else if(Cell.col>N)//East overflow
	{
		Cell.Direc[0]='W';
		Cell.col=N-fabs(Cell.col-N);
	}
	return(0);
}
/*judge the two cell whether have collition*/
bool IsCollision(Rabbit &Cell1,Rabbit &Cell2)
{
	if(Cell1.row==Cell2.row&&Cell1.col==Cell2.col)
	{
		return(true);
	}	
	else
	{
		return(false);
	}
}
/*change the direction each other*/
int Collision(Rabbit &Cell1,Rabbit &Cell2)
{
	char temp=Cell1.Direc[0];
	Cell1.Direc[0]=Cell2.Direc[0];
	Cell2.Direc[0]=temp;
	return(0);
}
/*cell trun the left*/
int TurnLeft(Rabbit &Cell)
{
	switch(Cell.Direc[0])
	{
		case 'N':
		Cell.Direc[0]='W';
		break;
		case 'E':
		Cell.Direc[0]='N';
		break;
		case 'S':
		Cell.Direc[0]='E';
		break;
		case 'W':
		Cell.Direc[0]='S';
		break;
	}
	return(0);
}
/*for test*/
int test()
{
	return(0);
}
/*main process*/
int MainProc()
{
	while(scanf("%d",&N)!=EOF&&N)//from 1 to N
	{
		scanf("%s%d%d",Tom.Direc,&Tom.Speed,&Tom.hour);
		scanf("%s%d%d",Jerry.Direc,&Jerry.Speed,&Jerry.hour);
		scanf("%d",&K);
		Tom.row=1;
		Tom.col=1;
		Jerry.row=N;
		Jerry.col=N;
		int i=0;
		for(i=1;i<=K;i++)
		{
			MoveAhead(Tom);
			MoveAhead(Jerry);
			//collision with wall
			if(IsWall(Tom))
			{
				TurnAround(Tom);
			}
			if(IsWall(Jerry))
			{
				TurnAround(Jerry);
			}
			//collision each other
			if(IsCollision(Tom,Jerry))
			{
				Collision(Tom,Jerry);
			}
			else
			{
				//turn left
				if(i%Tom.hour==0)
				TurnLeft(Tom);
				if(i%Jerry.hour==0)
				TurnLeft(Jerry);
			}
		}
		printf("%d %d\n%d %d\n",Tom.row,Tom.col,Jerry.row,Jerry.col);
	}
	return(0);
}
int main()
{
	MainProc();
	return(0);
}

 

 

 

 

 

 

 

 

 

版权声明:本文为博主原创文章,未经博主允许不得转载。