注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

ZSTU 3426 Pablo Squarson's Headache  

2011-11-06 19:18:19|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

http://acm.zstu.edu.cn:8080/JudgeOnline/showproblem?problem_id=3426

Pablo Squarson's Headache

Time Limit:5000MS  Memory Limit:65536K
Total Submit:109 Accepted:57

Description

Pablo Squarson is a well-known cubism artist. This year's theme for Pablo Squarson is "Squares". Today we are visiting his studio to see how his masterpieces are given birth.

At the center of his studio, there is a huuuuuge table and beside it are many, many squares of the same size. Pablo Squarson puts one of the squares on the table. Then he places some other squares on the table in sequence. It seems his methodical nature forces him to place each square side by side to the one that he already placed on, with machine-like precision.

Oh! The first piece of artwork is done. Pablo Squarson seems satisfied with it. Look at his happy face.

Oh, what's wrong with Pablo? He is tearing his hair! Oh, I see. He wants to find a box that fits the new piece of work but he has trouble figuring out its size. Let's help him!

Your mission is to write a program that takes instructions that record how Pablo made a piece of his artwork and computes its width and height. It is known that the size of each square is 1. You may assume that Pablo does not put a square on another.

I hear someone murmured "A smaller box will do". No, poor Pablo, shaking his head, is grumbling "My square style does not seem to be understood by illiterates".


ZSTU 3426 Pablo Squarsons Headache - 东月之神 - 东月之神

Input

The input consists of a number of datasets. Each dataset represents the way Pablo made a piece of his artwork. The format of a dataset is as follows.

N
n1 d1
n2 d2
...
nN-1 dN-1

The first line contains the number of squares (= N) used to make the piece of artwork. The number is a positive integer and is smaller than 200.

The remaining (N-1) lines in the dataset are square placement instructions. The line “ni di” indicates placement of the square numbered i (≤ N-1). The rules of numbering squares are as follows. The first square is numbered "zero". Subsequently placed squares are numbered 1, 2, ..., (N-1). Note that the input does not give any placement instruction to the first square, which is numbered zero.

A square placement instruction for the square numbered i, namely “ni di”, directs it to be placed next to the one that is numbered ni, towards the direction given by di, which denotes leftward (= 0), downward (= 1), rightward (= 2), and upward (= 3).

For example, pieces of artwork corresponding to the four datasets shown in Sample Input are depicted below. Squares are labeled by their numbers.


ZSTU 3426 Pablo Squarsons Headache - 东月之神 - 东月之神

The end of the input is indicated by a line that contains a single zero.

Output

For each dataset, output a line that contains the width and the height of the piece of artwork as decimal numbers, separated by a space. Each line should not contain any other characters.

Sample Input

1  5  0 0  0 1  0 2  0 3  12  0 0  1 0  2 0  3 1  4 1  5 1  6 2  7 2  8 2  9 3  10 3  10  0 2  1 2  2 2  3 2  2 1  5 1  6 1  7 1  8 1  0  

Sample Output

1 1  3 3  4 4  5 6  

Source

Asia 2010,Japan domestic

         看题目倒是挺长的,图片还挺吓人的,不过也是一个水题。题意就是每个方块有一个编号,输入两个数,第一个是方块的编号,第二个是一个操作数,即在这个方块的上(3)下(1)左(0)右(2)安置另一个方块。然后要一个矩形可以把所有的小方块覆盖住。其实只要模拟如何放置,然后找出最大的和最小的x坐标,做大做小的y坐标就可以知道最后的矩形的宽和高了。而找最小最大的坐标在输入的时候就可以进行了。

代码如下:

#include <stdio.h>
#include <string.h>
struct squ
{
 int x, y, num;
}squ1[20];

int main()
{
 int n;
 while(scanf("%d", &n) != EOF)
 {
  if(n == 1){printf("1 1\n");continue;}
  if(n == 0) break;
  memset(squ1, 0, sizeof(squ1));
  int i, a, b, cnt = 1, j;
  int w1, w2, h1, h2;
  w1 = h1 = 230;
  w2 = h2 = -230; 
  if(squ1[0].x < h1) h1 = squ1[0].x;
  if(squ1[0].x > h2) h2 = squ1[0].x;
  if(squ1[0].y < w1) w1 = squ1[0].y;
  if(squ1[0].y > w2) w2 = squ1[0].y; 
  for(i = 1; i < n; i++)
  {
   scanf("%d%d", &a, &b);
   squ1[i].num = cnt;
   for(j = 0; j < i; j++)
   {
    if(squ1[j].num == a)
    {
     if(b == 0)
     {
      squ1[i].y = squ1[j].y-1;
      squ1[i].x = squ1[j].x;
     }
     else if(b == 1)
     {
      squ1[i].y = squ1[j].y;
      squ1[i].x = squ1[j].x+1;
     }
     else if(b == 2)
     {
      squ1[i].y = squ1[j].y+1;
      squ1[i].x = squ1[j].x;
     }
     else if(b == 3)
     {
      squ1[i].y = squ1[j].y;
      squ1[i].x = squ1[j].x-1;
     }
     if(squ1[i].x < h1) h1 = squ1[i].x;
     if(squ1[i].x > h2) h2 = squ1[i].x;
     if(squ1[i].y < w1) w1 = squ1[i].y;
     if(squ1[i].y > w2) w2 = squ1[i].y; 
     break;
    }
       
   } 
   cnt++;
  }
  printf("%d %d\n",  w2 - w1 + 1, h2 - h1 + 1);
 }
return 0;
}

  评论这张
 
阅读(141)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017