toj_2818.cpp

Tianjin University Online Judge 的80多道题目 .

/*2818.   Prairie dogs IV Time Limit: 10.0 Seconds   Memory Limit: 65536K
Total Runs: 116   Accepted Runs: 74


Oh, my God! The lovely prairie dogs come again! We know they are very naughty and always play some funny games. This time, they play a game named Spiral Queue.

Each of the prairie dogs has a number and they stand in a funny queue named Spiral Queue like in Figure 1.

Given the coordinate, the direction of x-axis and y-axis is indicated in Figure 2. We suppose the coordinate of 1 is (0,0), then the coordinate of 2 is (1,0), the coordinate of 3 is (1,1) and the coordinate of 7 is (-1,-1).

21   22  ...
20   7   8   9  10
19   6   1   2  11
18   5   4   3  12
17  16  15  14  13
      
      Figure1

Find out the laws of the Spiral Queue.

Your task is here: Given x and y (-1000 ≤ x,y ≤ 1000), the coordinate of a prairie dog, try to find out the number of the prairie dog.

Inpu*/
#include<cstdio>
#include<cstdlib>
#define MAXLEN 1000
 int map[ 2 * MAXLEN + 10 ][ 2 * MAXLEN + 10 ];

void printMap()
{
     int i , j;
     for ( i = 0; i <= 2 * MAXLEN + 1; i++ )
     {
        for ( j = 0; j <= 2 * MAXLEN + 1 ; j++ )
            printf( "%2hd " , map[ i ][ j ] );
            printf( "\n" );
     }
     system( "pause" );
}
int main()
{
  int count;
    int i , j , k , x , y, directionStep , len , direction , xIn , yIn;
   int dx[ 4 ] = { 1 , 0 , -1 , 0 }  , dy[ 4 ] = { 0 , 1 , 0 , -1 };
  map[ MAXLEN ][ MAXLEN ] = 1;
  for( direction = 0 , count = 1 , x = MAXLEN,  y  = MAXLEN, len = 1; len <= 2 * MAXLEN + 2 ;  len++ )
    {
      for ( i = 0; i < 2; i++ )
	{
	  for ( j = 0; j < len; j++ )
	    {
	      x += dx[ direction ];
	      y += dy[ direction ];
	      map[ y ][ x ] = ++count;
	    }
	  direction = ( direction + 1 ) % 4;
	}
    }
  while ( scanf( "%d%d" , &xIn , &yIn ) != EOF )
    {
      printf( "%d\n" , map[ xIn + MAXLEN ][ yIn + MAXLEN ] );
    }
  return 0;
}