AOJ-ICPC 1174

友人に勧められてこの問題に挑戦しました。

Identically Colored Panels Connection | Aizu Online Judge

w*hマスのパネルがあります。それぞれのパネルは6種の色のうちの1色が塗られています。
左上のパネルには電気を通すことができ、そうすることで６色のうち好きな色に変えることができます。
また、隣り合うパネルが同じ色であった場合はそのパネル同士がくっついて一つになります。電気を通せばくっついたパネルも色が変わります。
このような性質のパネルについて、電気を5回通して指定された色でできるだけ大きな領域を作りましょう、という問題です。

解答はこちら。二日かかりました。

#include <cstdio>
#include <iostream>
#include <cmath>
#include <ctype.h>
#include <string> 
#include <sstream>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <map>
#include <queue>
#include <utility>
#include <vector>
#include <set>
  
using namespace std;
 
void changepanel(int ***p, int px, int py, int newc, int t);
int count(int ***p, int t, int color, int x, int y);
void simulate(int ***p, int t);
bool isedge(int ***p, int x, int y, int t);
 
int h, w, c;
 
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
 
int ans;
 
// 縁なのか確認したかどうか
bool ischecked[8][8];
// パネルの色が変更されたかどうか
bool ischanged[8][8];
// そのパネルをカウントしたかどうか
bool iscounted[8][8];
 
int main()
{
    while(1){
        cin >> h >> w >> c;
        if(h == 0) break;
        ans = 0;
　　　　// メモリ確保
        int ***panel = new int**[h];
        for(int i = 0; i < h; i++) panel[i] = new int*[w];
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                panel[i][j] = new int[6];
            }
        }
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> panel[i][j][0];
            }
        }
        simulate(panel, 1);
        cout << ans << endl;
        // メモリ解放
        delete[] panel;
    }
    return 0;
}
 
void changepanel(int ***p, int px, int py, int newc, int t)
{
    int nextx, nexty;
    int beforecolor = p[px][py][t];
    p[px][py][t] = newc;
    ischanged[px][py] = true;
    for(int i = 0; i < 4; i++){
        nextx = px + dx[i];
        nexty = py + dy[i];
        if(nextx >= h || nextx < 0 || nexty >= w || nexty < 0) continue;
        if(p[nextx][nexty][t] == beforecolor && !ischanged[nextx][nexty]) changepanel(p, nextx, nexty, newc, t);
    }
    return;
}
 
int count(int ***p, int t, int color, int x, int y)
{
    // 深さ優先探索で領域の大きさを数える
    int ans = 0;
    if(iscounted[x][y]) ans++;
    for(int i = 0; i < 4; i++){
        int nextx = x + dx[i], nexty = y + dy[i];
        if(nextx >= h || nextx < 0 || nexty >= w || nexty < 0) continue;
        else if(p[nextx][nexty][t] == color && !iscounted[nextx][nexty]){
            iscounted[nextx][nexty] = true;
            ans += count(p, t, color, nextx, nexty);
        }else if(p[nextx][nexty][t] == c && !iscounted[nextx][nexty]){
            iscounted[nextx][nexty] = true;
            ans += count(p, t, c, nextx, nexty);
        }
    }
    return ans;
}
 
void simulate(int ***p, int t)
{
　　// 以下のifはいらない？
    if(w == 1 && h == 1){
        ans = 1;
        return;
    }
    if(t == 5) {
        for(int i = 1; i < 7; i++){
　　　　　　// iscountedをリセット
            for(int j = 0; j < h; j++){
                for(int k = 0; k < w; k++){
                    iscounted[j][k] = false;
                }
            }
            if(p[0][0][t] == i) iscounted[0][0] = true;
            int a = 0;
            a = count(p, t - 1, i, 0, 0);
            ans = max(ans, a);
            }
        return;
    }
　　// 一つ前の状態をコピーする
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            p[i][j][t] = p[i][j][t - 1];
        }
    }
    int x = 0, y = 0;
    while(1){
        // xを1ずつ増加、xがhまで達したらyを1増加させxを0にする(上から下、左から右へ調べる)
        if(y == w) break;
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                ischecked[i][j] = false;
                ischanged[i][j] = false;
            }
        }
        ischecked[x][y] = true;
　　　　// (x, y)の色が(0, 0)と一致せず、かつ(x, y)が(0, 0)を含む領域の縁である場合
　　　　// →(x, y)の色に変えれば領域が広がる
        if(p[x][y][t] != p[0][0][t] && isedge(p, x, y, t)){
            for(int i = 0; i < h; i++){
                for(int j = 0; j < w; j++){
　　　　　　　　　　// パネルを一つ前の状態に戻す
                    p[i][j][t] = p[i][j][t - 1];
                }
            }
            int newc = p[x][y][t];
            changepanel(p, 0, 0, newc, t);
            simulate(p, t + 1);
        } else {
            x++;
            if(x == h){
                y++;
                x = 0;
            }
        }
    }
    simulate(p, t + 1);
}
// あるパネルについて、隣り合ってるパネルの色以外の色でぬりかえることは無意味
 
bool isedge(int ***p, int x, int y, int t)
{
　　// (x, y)から(0, 0)の色と一緒のパネルを辿っていき、(0, 0)にたどり着いたらtrueを返すようにする
    if(x == 0 && y == 0) return true;
    bool ans = false;
    for(int i = 0; i < 4; i++){
        int nextx = x + dx[i];
        int nexty = y + dy[i];
        if(nextx >= h || nextx < 0 || nexty >= w || nexty < 0) continue;
        if(p[nextx][nexty][t] == p[0][0][t] && !ischecked[nextx][nexty]){
            ischecked[nextx][nexty] = true;
            ans = isedge(p, nextx, nexty, t);
            if(ans) break;
        }
    }
    return ans;
}

5回パネルを変更させる、ということですが4回までのぬりかえでok。5回目ではそれまででできたうち一番大きな領域を指定された数で塗りつぶせば大丈夫です。
(0, 0)から領域の縁となっているパネルを見つけたらそのパネルの色に領域の色を変更させてみて…というのを全通り試します。
このうち、1から6のうち一番数の多いものを見つけ、それらのうちさらに一番大きいものが答えとなります。

ischeckedとかischangedを作ってなかったのでsegmentation faultに苦しめられました。
しんどい。
でも初めて難易度350の問題が解けたので嬉しいですね。