問題文は↑を、と言いたいところなのですが僕は読めなかったので、 AOJ : 1235 - Life Line - Respect2Dの日記を参考にさせて頂きました。丁寧な説明本当に助かります。
まあやるだけなわけですが、cと同じ番号のを多めに引いて後で足すって形でなんとか
してます。
1WA(しかも今までAC率100%だったのにそうじゃなくなった)したのは内緒。
#include <cstdio> #include <cstring> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define INF (1<<21) #define max(a,b) (a<b?b:a) int v[10][10]; int N; int dx[] = {0,1,0,-1,-1,1}; int dy[] = {1,1,-1,-1,0,0}; bool done[10][10] = {0}; bool chk(int x,int y,int num,int &c){ if(y < 0 || x >= y+1 || x < 0 || y >= N) return false; if(!v[y][x])return true; if(num != v[y][x])return false; if(done[y][x])return false; else done[y][x] = true; c++; bool ans = false; rep(i,6) ans |= chk(x+dx[i],y+dy[i],num,c); return ans; } int solve(int c){ int ans = -INF; rep(i,N){ rep(j,i+1){ int sum = 0; memset(done,0,10*10); if(v[i][j]) continue; v[i][j] = c; int a=0; if( !chk(j,i,v[i][j],a) ) sum -= 2*a; memset(done,0,10*10); rep(y,N)rep(x,y+1){ if( done[y][x] || !v[y][x])continue; int b = 0; if( !chk(x,y,v[y][x],b) )sum += b; } v[i][j] = 0; ans = max(ans,sum); } } return ans; } int main(){ int c; while(scanf("%d %d",&N,&c) && N || c){ rep(i,N)rep(j,i+1) scanf("%d",&v[i][j]); printf("%d\n",solve(c)); } }