AOJ : 1174 - 同色パネル結合 (Identically Colored Panels Connection)
問題概要
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1174&lang=jp
日本語の問題文があるので, 説明省略です
アルゴリズム
左上のマスを1〜6に変える処理を再帰で書きます.
ただし, 5回目に色を変えるときだけ入力で与えられたCに変えます.
色を変えたときは, 幅優先でマップを書き変え.
最後にパネルの数をカウントするときも, 幅優先でカウント.
プログラム
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> P; int h,w,c; int dx[] = {1,-1,0,0}; int dy[] = {0,0,1,-1}; int area(vvi &v){ int res = 0; int color = v[0][0]; queue<P> open; bool closed[h][w]; memset(closed,0,sizeof(closed)); open.push(P(0,0)); while(!open.empty()){ P p = open.front(); open.pop(); if(closed[p.second][p.first]) continue; closed[p.second][p.first] = true; res++; rep(i,4){ int nx = p.first + dx[i]; int ny = p.second + dy[i]; if(nx>=0 && w>nx && ny>=0 && h>ny && v[ny][nx]==color){ open.push(P(nx,ny)); } } } return res; } vvi draw(vvi v,int nextColor){ int firstColor = v[0][0]; queue<P> open; bool closed[h][w]; memset(closed,0,sizeof(closed)); open.push(P(0,0)); while(!open.empty()){ P p = open.front(); open.pop(); if(closed[p.second][p.first]) continue; closed[p.second][p.first] = true; v[p.second][p.first] = nextColor; rep(i,4){ int nx = p.first + dx[i]; int ny = p.second + dy[i]; if(nx>=0 && w>nx && ny>=0 && h>ny && v[ny][nx]==firstColor){ open.push(P(nx,ny)); } } } return v; } int solve(vvi v,int rem){ if(rem == 0){ return area(v); } int res = 0; REP(i,1,7){ if(rem == 1 && i != c) continue; res = max(res,solve(draw(v,i),rem-1)); } return res; } int main(){ while(cin>>h>>w>>c,h||w||c){ vvi v(h); rep(i,h){ v[i] = vi(w); rep(j,w) cin>>v[i][j]; } cout<<solve(v,5)<<endl; } }