AOJ 1174 Identically Colored Panels Connection
問題
問題文読んで。
解法
色の変化をdfsする。隣接するマスの判定もdfsで。
コード
int h,w,c; int dx[4] = {1,0,-1,0}; int dy[4] = {0,-1,0,1}; int p[8][8]; bool ck[8][8]; bool valid(int x, int y){ return x>=0&&x<w&&y>=0&&y<h; } void check(int x, int y, int c){ if(ck[y][x]||p[y][x]!=c) return; ck[y][x] = true; REP(r,4){ int nx = x+dx[r]; int ny = y+dy[r]; if(valid(nx,ny)){ check(nx,ny,c); } } } int dfs(int t){ int ret = 0; if(t==5){ memset(ck,0,sizeof(ck)); check(0,0,c); REP(y,h)REP(x,w)if(ck[y][x])ret++; }else{ int tmp[8][8]; memcpy(tmp,p,sizeof(p)); REP(nc,6){ memset(ck,0,sizeof(ck)); check(0,0,p[0][0]); REP(y,h)REP(x,w)if(ck[y][x])p[y][x] = nc; ret = max(ret,dfs(t+1)); memcpy(p,tmp,sizeof(tmp)); } } return ret; } int main(){ while(cin>>h>>w>>c,h){ c--; REP(y,h)REP(x,w)cin>>p[y][x],p[y][x]--; cout<<dfs(0)<<endl; } return 0; }