ICPC 国内予選2011C 同色パネル結合 AOJ 1174

パネルの変更の組み合わせを全通り試せばよい。（6^5 < 10^5　だから計算量は余裕）

結合パネルかどうかはunion-findで判定すれば楽。

#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;
 
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;
 
const ll MOD=1e9+7;
const ll INF=1e18;
 
int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};


int par[110];//親
int rank2[110];//木の深さ

void init(int n){
  for(int i = 0;i < n;i++){
    par[i] = i;
    rank2[i] = 0;
  }
}

int find(int x){
  if(par[x] == x){
    return x;
  }else{
    return par[x] = find(par[x]);
  }
}

void unite(int x,int y){
  x = find(x);
  y = find(y);
  if(x == y) return;
  
  if(rank2[x] < rank2[y]){
    par[x] = y;
  }else{
    par[y] = x;
    if(rank2[x] == rank2[y])rank2[x]++;
  }
}

bool same(int x,int y){
  return find(x) == find(y);
}
  




int h,w,c;
int p[12][12];
int ban[7];

int main(){
    while(true){
        cin >> h >> w >> c;
        if(h + w + c == 0)break;
        for(int i = 1;i <= h;i++){
            for(int j = 1;j <= w;j++){
                cin >> p[i][j];
            }
        }
        for(int j = 0;j <= w+1;j++){
            p[0][j] = -1;
            p[h+1][j] = -1;
        }
        for(int i = 0;i <= h+1;i++){
            p[i][0] = -1;
            p[i][w+1] = -1;
        }
        int ans = 0;
        for(int n = 11111;n <= 66666;n++){
            int maxban = -1;
            int div = 1;
            for(int i = 1;i <= 5;i++){
                ban[i] = (n / div) % 10;
                maxban = max(maxban,ban[i]);
                div *= 10;
            }
            if(maxban >= 7)continue;
            init(80);

            int tmpans = 0;
            queue<P> que;
            que.push(P(1,1));
            tmpans++;
            while(!que.empty()){
                P q = que.front(); que.pop();
                for(int k = 0;k < 4;k++){
                    int ni = q.fs + dy[k],nj = q.sc + dx[k];
                    if(p[ni][nj] == p[1][1] && same(1,w*(ni-1)+nj) == false){
                        tmpans++;
                        unite(1,w*(ni-1)+nj);
                        que.push(P(ni,nj));
                    }
                }
            }

            for(int l = 1;l <= 5;l++){
                for(int i = 1;i <= h;i++){
                    for(int j = 1;j <= w;j++){
                        if(same(1,w*(i-1)+j)){
                            que.push(P(i,j));
                        }
                    }
                }
                while(!que.empty()){
                  P q = que.front(); que.pop();
                  for(int k = 0;k < 4;k++){
                    int ni = q.fs + dy[k],nj = q.sc + dx[k];
                    if(p[ni][nj] == ban[l] && same(1,w*(ni-1)+nj) == false){
                      tmpans++;
                      unite(1,w*(ni-1)+nj);
                      que.push(P(ni,nj));
                    }
                  }
                }
            }
            if(ban[5] == c){
              ans = max(ans,tmpans);
            }
        }
        cout << ans << endl;
    }
}