PKU 3338 Rectangle Cutting

比较烦人的模拟

#include<stdio.h>
2

#include<string.h>
3

char xy[30][30],yx[30][30],use[30][30];
4

int n,m;
5

void di(int x,int y)
6

{
7

if(x>=m||y>=n)return;
8

use[x][y]=0;
9

//printf("%d %d\n",x,y);
10

if(xy[x][y+1]&&use[x-1][y])di(x-1,y);
11

if(xy[x+1][y+1]&&use[x+1][y])di(x+1,y);
12

if(yx[y+1][x+1]&&use[x][y+1])di(x,y+1);
13

if(yx[y][x+1]&&use[x][y-1])di(x,y-1);
14

}
15

int main()
16

{
17

int ans,i,k,x1,x2,y1,y2,t,j;
18

while(scanf("%d%d",&n,&m),n)
19

{
20

memset(xy,1,sizeof(xy));
21

memset(use,1,sizeof(use));
22

memset(yx,1,sizeof(yx));
23

ans=0;
24

for(i=1;i<=m;i++)yx[0][i]=0;
25

for(i=1;i<=m;i++)yx[n][i]=0;
26

for(i=1;i<=n;i++)xy[0][i]=0;
27

for(i=1;i<=n;i++)xy[m][i]=0;
28

scanf("%d",&k);
29

while(k--)
30

{
31

scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
32

if(x1>x2){t=x1;x1=x2;x2=t;}
33

if(y1>y2){t=y1;y1=y2;y2=t;}
34

// printf("asdasdasdas%d %d\n",x1,y1);
35

for(i=y1+1;i<=y2;i++)xy[x1][i]=0;
36

for(i=y1+1;i<=y2;i++)xy[x2][i]=0;
37

for(i=x1+1;i<=x2;i++)yx[y1][i]=0;
38

for(i=x1+1;i<=x2;i++)yx[y2][i]=0;
39

}
40

// printf("asdasdasdas%d\n",xy[1][1]);
41

for(i=0;i<m;i++)
42

for(j=0;j<n;j++)
43

{
44

if(use[i][j] && (xy[i][j+1] || xy[i+1][j+1] || yx[j][i+1] || yx[j+1][i+1]))
45

{
46

//printf("******************\n");
47

di(i,j);
48

ans++;
49

}
50

}
51

for(i=0;i<m;i++)
52

for(j=0;j<n;j++)if(use[i][j])ans++;
53

printf("%d\n",ans);
54

}
56

return 0;
57

}
58

posted on 2008-07-18 16:46 gong 阅读(192) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。




网站导航: 博客园博客园最新博文博问管理

2008年7月

日

一

二

三

四

五

六

统计

随笔 - 50
文章 - 0
评论 - 22
引用 - 0

常用链接

留言簿(6)

随笔档案

搜索

积分与排名

积分 - 29954
排名 - 669