[搜索]OI練習題：求圖形面積 area

題一 求圖形面積

【問題描述】

具有不同顏色的 N 個小的矩形的紙被疊放在一張白紙上， 紙的尺寸是寬(左右)為A， 長(上下)為B，擺放矩形時使矩形的邊與紙的邊平行，並且每個矩形必須整個放在紙的邊界之內。因此，不同顏色的各種不同圖形可在紙上出現，同一顏色的兩個區域中如果至少有一個公共點，則認為它們是同一圖形的一部分，否則認為是不同的圖形。

題目要求計算每一圖形的面積。 A ， B 是正的偶數，且均不大於30 。座標系統的定義為：座標原點在紙的中心，兩個軸分別平行於紙的兩邊。

【輸入格式】

輸入資料在文件中，其組成如下：

首行是 A,B,N , 中間用空格隔開,分別為寬和長及矩形的個數;

接下來有 N 行，每行有 空格隔開的 5 個資料，分別表示矩形左下角的橫座標、縱座標、矩形右上角的橫座標、縱座標、矩形的顏色（用 1-64 分別來表示一共的 64 種顏色，其中 1 表示白色）。

【輸出格式】

要求每行輸出一個彩色圖形的顏色和對應圖形的面積，按顏色代碼的升序安排記錄的輸出順序。(若有顏色相同的不同圖形,先輸出靠上靠左的圖形)

【輸入輸出樣例】

輸入文件名： area.in

20 12 5

-7 -5 -3 -1 4

-5 -3 5 3 2

-4 -2 -2 2 4

2 -2 3 -1 12

3 1 7 5 1

輸出文件名：area.out

1 172

2 47

4 12

4 8

12 1

【分析】
這是一個很簡單、很老的題目了，我初學BFS的時候老師就讓我們看這道題目了。但是由於這個題的一些細節很煩人，一直沒有AC，所以今天抽出一點時間，終於把這道題AC了～

題目說的很清楚了，就是一個FloodFill。

由於坐標中存在負數，所以要給每個坐標的X加上A/2,Y加上B/2使其變為整數。

雖然題目中說“同一顏色的兩個區域中如果至少有一個公共點，則認為它們是同一圖形的一部分，否則認為是不同的圖形”但是這句話是坑人的！其實不必有公共點，如下圖：

 

按題目的說法，這個圖上有2塊“2”的區域，但是測試數據把它當作1塊來算了～於是，我就被騙了近1年～～

還有，題目中說“若有顏色相同的不同圖形,先輸出靠上靠左的圖形”，所以，一定要注意枚舉的順序，否則只能A 3組數據。

最後修訂：12:28 Jan20,2012

【我的代碼】

裸代碼

C++语言: Codee#25336

001 /*
002 *Problem:信息學競賽練習題：求圖形面積
003 *Author: Yee-fan Zhu
004 *Data: Jan 20th,2012
005 *Method: FloodFill BFS
006 */
007 #include <cstdio>
008 #include <cstdlib>
009 #include <iostream>
010 #include <vector>
011 #include <queue>
012 using namespace std;
013 const int step[9][2]={{0,0},{-1,0},{1,0},{0,1},{0,-1},{1,-1},{1,1},{-1,1},{-1,-1}};
014 int Map[40][40];
015 int A,B,N;
016 int ADDX;
017 int ADDY;
018 class Color
019 {
020 public:
021     int Col;
022     int Num;
023 };
024 vector<Color>C;
025
026 void print()
027 {
028     for (int k=1;k<=64;k++)
029     {
030         for (unsigned int i=0;i<C.size();i++)
031             if(C[i].Col==k)
032                 printf("%d %d\n",C[i].Col,C[i].Num);
033     }
034 }
035
036 void init()
037 {
038     scanf("%d %d %d\n",&A,&B,&N);
039    
040     ADDX=A/2;
041     ADDY=B/2;
042    
043     for (int i=1;i<=B;i++)
044         for (int j=1;j<=A;j++)
045             Map[i][j]=1;
046    
047     int x1,x2,y1,y2,c;
048     for (int i=1;i<=N;i++)
049     {
050         scanf("%d %d %d %d %d\n",&x1,&y1,&x2,&y2,&c);
051         x1+=ADDX,y1+=ADDY,x2+=ADDX,y2+=ADDY;
052         for(int k=x1+1;k<=x2;k++)
053             for (int j=y1+1;j<=y2;j++)
054                 Map[j][k]=c;
055     }
056 }
057
058 class QUEUE
059 {
060 public:
061     int x,y;
062 };
063
064 queue<QUEUE>Q;
065
066 int bfs(int x,int y)
067 {
068     int Ans=1;
069     int Co=Map[x][y];
070     Map[x][y]=-1;
071     while(!Q.empty())
072         Q.pop();
073     QUEUE tmp;
074     QUEUE next;
075     tmp.x=x,tmp.y=y;
076     Q.push(tmp);
077     int tx,ty;
078     int nx,ny;
079    
080     while(!Q.empty())
081     {
082         tmp=Q.front();
083         Q.pop();
084         tx=tmp.x,ty=tmp.y;
085         for (int i=1;i<=8;i++)
086         {
087             nx=tx+step[i][0];
088             ny=ty+step[i][1];
089             if(nx>=1 && nx<=B && ny>=1 && ny<=A )
090             {
091                 if(Map[nx][ny]==Co)
092                 {
093                     Ans++;
094                     next.x=nx;
095                     next.y=ny;
096                     Map[nx][ny]=-1;
097                     Q.push(next);
098                 }
099             }
100         }
101     }
102     return Ans;
103 }
104
105 void work()
106 {
107     for (int j=1;j<=A;j++)
108     {
109         for (int i=1;i<=B;i++)
110         {
111             if(Map[i][j]!=-1)
112             {
113                 int co=Map[i][j];
114                 int num=bfs(i,j);
115                 Color tmp;
116                 tmp.Col=co;
117                 tmp.Num=num;
118                 C.push_back(tmp);
119             }
120         }
121     }
122 }
123
124 int main()
125 {
126     freopen("area.in","r",stdin);
127     freopen("area.out","w",stdout);
128     init();
129     work();
130     print();
131     return 0;
132 }