AOJ 1174: Identically Colored Panels Connection

問題

Identically Colored Panels Connection | Aizu Online Judge

• 電気を流すと隣接した同じ色のパネルを含めて色が変わるパネルがある
• 隣接した同じ色のパネルは結合する
• 左上のパネルに5回電気を流したとき、指定された色で左上と結合している最大のパネル数を求めよ

方針

• dfsであらゆる変色パターンを試す (6の5乗なので間に合いそう）
• パネルの変色とパネル数カウントはbfsでやる

コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)

typedef pair<int, int> P;

int p[10][10], visited[10][10];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int h, w, c;

int dfs(int count) {
    if(count == 5) {
        int ret = 0;
        if(p[0][0] != c) return 0;
        rep(i, 10) rep(j, 10) visited[i][j] = 0;
        queue<P> que;
        que.push(P(0, 0));
        while(!que.empty()) {
            P point = que.front(); que.pop();
            if(visited[point.first][point.second] == 0) {
               visited[point.first][point.second] = 1;
               ret++;
                rep(i, 4) {
                    int ny = point.first + dy[i];
                    int nx = point.second + dx[i];
                    if(nx >= 0 && nx < w && ny >= 0 && ny < h &&
                       visited[ny][nx] == 0 && p[ny][nx] == c) {
                        que.push(P(ny, nx));
                    }
                }
            }
        }
        return ret;
    }
    int org[10][10];
    int ret = 0;
    rep(i, h) rep(j, w) org[i][j] = p[i][j];
    rep(color, 6) {
        int org_c = p[0][0];
        rep(i, 10) rep(j, 10) visited[i][j] = 0;
        queue<P> que;
        que.push(P(0, 0));
        while(!que.empty()) {
            P point = que.front(); que.pop();
            p[point.first][point.second] = color+1;
            visited[point.first][point.second] = 1;
            rep(i, 4) {
                int ny = point.first + dy[i];
                int nx = point.second + dx[i];
                if(nx >= 0 && nx < w && ny >= 0 && ny < h &&
                   visited[ny][nx] == 0 && p[ny][nx] == org_c) {
                    que.push(P(ny, nx));
                }
            }
        }
        ret = max(ret, dfs(count+1));
        rep(i, 10) rep(j, 10) p[i][j] = org[i][j];
    }
    return ret;
}

int main(void){
    while(cin >> h >> w >> c && h) {
        rep(i, h) rep(j, w) cin >> p[i][j];
        cout << dfs(0) << endl;
    }
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1920825

反省

• visitedの処理がうまく書けなくて重複カウントしていてハマった
• 遅い(1.7s)のは仕方ないのかなと思ったら、同じような解法でもvisitedの更新をしないで済むよう実装すれば0.02sで解けていた（これとか）