ACM-ICPC 2011年 国内予選 問題C 同色パネル結合

問題C:同色パネル結合

色は5回まで変えられる。また、5回目に変える色は指定されている。だから、「1～4回目の色の組み合わせ+1色」についてパネルの強度を調べ、最大を求める。色の数が6色なので、大雑把に考えて計算量はO(6^4)となる。コードでは、色の組み合わせを6進数4桁の数として考え、解いている。

実際に提出したコードではなく、清書したものなので、確認した入力はサンプルインプットのみ。確認済。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int h, w, c;
int panel[10][10];
int buf[10][10];

int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

int tl_corner;
int change;

void paint(int y, int x)
{
    if (change == tl_corner)    return;
    if (!(0 <= y && y < h))     return;
    if (!(0 <= x && x < w))     return;
    if (buf[y][x] != tl_corner) return;

    buf[y][x] = change;
    for (int i = 0; i < 4; i++)
        paint(y+dy[i], x+dx[i]);
}

int count(int y, int x)
{
    if (!(0 <= y && y < h))     return 0;
    if (!(0 <= x && x < w))     return 0;
    if (buf[y][x] != tl_corner) return 0;

    buf[y][x] = -1;
    int ans = 1;
    for (int i = 0; i < 4; i++)
        ans += count(y+dy[i], x+dx[i]);
    return ans;
}

int solve(int *colors)
{
    for (int i = 0; i < 5; i++) {
        tl_corner = buf[0][0];
        change = colors[i];
        paint(0, 0);
    }

    tl_corner = c;
    return count(0, 0);
}

int main()
{
    while (cin >> h >> w >> c, h|w|c) {
        for (int y = 0; y < h; y++)
            for (int x = 0; x < w; x++)
                cin >> panel[y][x];

        int ans = 0;
        for (int i = 0; i < 6*6*6*6; i++) {
            int colors[5];
            for (int t = i, j = 0; j < 4; j++, t /= 6)
                colors[j] = t%6 + 1;
            colors[4] = c;

            memcpy(buf, panel, sizeof(panel));
            ans = max(ans, solve(colors));
        }
        cout << ans << endl;
    }
    return 0;
}