随笔 - 40, 文章 - 0, 评论 - 19, 引用 - 0
数据加载中……

PKU 3338 Rectangle Cutting

呵呵,这个题目做出来时候很开心,因为用到了一个小技巧,就是标记格子时候用2进制的变化规则来存储,这样绝不会出现重复,而这个数字最大是2^50,所以要用GCC/G++的long long型C/C++的__int64来存储。呵呵,这样做就只需要判格子即可不需要判边,最后一个DFS查数量就AC了,但是这是数据量范围决定的,>64的就没法这样做了~注意输入数字的大小顺序和自己的程序不符的时候要判断并互换才可以。
附上AC代码,呵呵,blog建立到现在有好几十的阅读量了,很高兴。我在ACM上还是个最菜的级别~希望能通过这个Blog坚持下去,并与大家交流得以提高&&认识些朋友~呵呵,希望大家留个言哈``

 1#include<stdio.h>
 2#include<string.h>
 3long long cake[20][20];
 4int used[20][20];
 5long long now;
 6int w,h;
 7long long po(int a , int  b ){
 8     long long temp;
 9     temp = 1 ; 
10     for(int i = 0 ; i < b ; i++){
11     temp = 2*temp;
12     }

13     return temp;
14}

15
16void dfs(int j , int i ){
17if(i<0||j<0||i>=w||j>=h) return;
18if(used[j][i]!=0)        return;
19if(cake[j][i]!=now)      return;
20used[j][i]=1;
21dfs(j+1,i);
22dfs(j-1,i);
23dfs(j,i+1);
24dfs(j,i-1);
25}

26
27int main(){
28    int count;
29    int t;
30    long long im;
31    int n;
32    int x1,x2,y1,y2;
33    while(scanf("%d%d",&w,&h)&&w&&h){
34    scanf("%d",&n);
35    memset(cake,-1,sizeof(cake));
36    memset(used,-1,sizeof(used));
37    count=0;
38    for(int i = 0 ; i < w ; i++ )
39    for(int j = 0 ; j < h ; j++ )
40   { cake[j][i] = 0 ;
41     used[j][i] = 0 ;
42   }

43    for(int i = 0 ; i < n ; i++ ){
44    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
45    
46    if (x1>x2) {t=x1;x1=x2;x2=t;}
47    if (y1>y2) {t=y1;y1=y2;y2=t;}
48    
49      forint j = x1 ; j < x2 ; j++ ){
50           for ( int k = y1 ; k < y2 ; k++ ){
51               cake[j][k] += po(2,i);
52           }
     
53      }
      
54    }

55    for(int i = 0 ; i < w ; i++ )
56    for(int j = 0 ; j < h ; j++ )
57    if(used[j][i]==0){
58    now=cake[j][i];
59    dfs(j,i);
60    count++;
61    }

62    printf("%d\n",count);
63    }

64return 0;
65}

66
67

posted on 2008-07-18 22:27 hadn't 阅读(375) 评论(1)  编辑 收藏 引用

评论

# re: PKU 3338 Rectangle Cutting  回复  更多评论   

留言,哈哈,今天我也起晚了
2008-07-20 10:32 | 未央

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理