[ZJ] d537. 第四題：染色遊戲＠Morris' Blog

2012-08-16 08:48:39| 人氣2,172| 回應0 | 上一篇 | 下一篇

[ZJ] d537. 第四題：染色遊戲

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

在一塊 NxN 的白布上，固定的位置上有幾支滴墨管。墨水的顏色有黃色(Yellow),藍色(Blue),以及紅色(Red)。按照一般彩色混色的原理如圖三，等量的黃色與藍色可以混出綠色；黃色與紅色則可以混出橘色。當一個地方被三種顏色染色時，則白布呈現黑色。顏色代碼分別是 (R=紅色,Y=黃色,B=藍色,O=橘色,G=綠色,P=紫色,D=黑色)。

當墨水被滴到白布上時，墨水會以一定的速度擴散開來。為了簡化問題，讓我們假設擴散的方式是以正方形的方式進行。如下途中，在一個白布上點了藍色的墨水，在時間t=0，只有中間一個籃點。等到 t=1 時，藍色則會擴散到如右圖的範圍。

假設白布的左下角空白格座標為(0,0)，而且所有滴墨管同時於t=0的時間滴下墨水。下圖是一個擴散的例子：滴黃色於(1,1)，藍色於(3,3)，紅色於(4,0)。

給你一塊白布、三支滴墨管(紅,黃,藍各一支)的座標以及一個顏色 X。請你寫一個程式告訴我們顏色 X 在白布曾出現過的最大面積為何？在上述擴散例子中，顏色 Y 曾出現的最大面積為8。

輸入說明：

第一行有一個正整數 N(N<=100)，N代表白布邊長。
第二行到第四行是每行依序顯示墨水管的顏色以及座標位置(顏色與座標值以一個空白分開)。
第五行為顏色 X。顏色 X可以是 (R,Y,B,O,P,G,D) 其中的任何一色。

輸出說明：

輸出顏色 X 在白布上曾出現過的最大面積。

範例輸入： help

輸入範例一：
5
Y 1 1
B 3 3
R 4 0
Y
輸入範例二：
5
Y 1 1
B 3 3
R 4 0
G

範例輸出：

輸出範例一：
8
輸出範例二：
9

提示：

出處：

台北縣98資訊學科能力競賽 (管理：pcshic)

我想看一下程式碼, 你便會理解我是怎麼做的

#include <stdio.h>

int main() {
    int n;
    while(scanf("%d", &n) == 1) {
        int ans = 0, i, j, k, t;
        char c[3][3], J[3];
        int x[3], y[3];
        for(i = 0; i < 3; i++)
            scanf("%s %d %d", &c[i], &x[i], &y[i]);
        scanf("%s", &J);
        int judge = 0;
        switch(J[0]) {
            case 'R':judge = 1;break;
            case 'Y':judge = 2;break;
            case 'B':judge = 4;break;
            case 'O':judge = 3;break;
            case 'P':judge = 5;break;
            case 'G':judge = 6;break;
            case 'D':judge = 7;break;
        }
        for(t = 0; t <= n; t++) {
            int color[8] = {};
            for(i = 0; i < n; i++) {
                for(j = 0; j < n; j++) {
                    int RYB = 0;
                    for(k = 0; k < 3; k++) {
                        int lx = x[k]-t, rx = x[k]+t;
                        int ly = y[k]-t, ry = y[k]+t;
                        if(lx <= i && i <= rx && ly <= j && j <= ry) {
                            if(c[k][0] == 'R') RYB |= 1;
                            if(c[k][0] == 'Y') RYB |= 2;
                            if(c[k][0] == 'B') RYB |= 4;
                        }
                    }
                    color[RYB]++;
                }
            }
            if(color[judge] > ans)
                ans = color[judge];
        }
        printf("%d\n", ans);
    }
    return 0;
}

我要檢舉

#d537#第四題#染色遊戲

台長： Morris

您可能對以下文章有興趣

[ZJ] d372. 4. 合法執行路徑問題

d913. 1. 彈珠配置

[ZJ][二分+凸包計算面積] b221. 6. 耕者有其田

[ZJ][BFS] d373. 5. 乳酪的誘惑

人氣(2,172) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ZJ][DP] a365. 3. 新井字遊戲
此分類上一篇:[ZJ] d372. 4. 合法執行路徑問題

回應(0)