给一个正三角形, 可以在任意一个 0 的地方填上数字 c ，填完之后计算出得分的最大值。
计算得分的规则：
相同数字的连通的集合 如果和某个0连通，就忽略了。
如果没有和0连通，分2种情况： 如果这个数字是c 则得分减去 这个集合中数字的个数，否则加上。
#include<cstdio> #include<cstring> #define MAX(x,y) ((x)>(y)?(x):(y)) int mov[6][2]={{0,-1},{0,1},{-1,-1},{-1,0},{1,0},{1,1}}; int flag,n,c,vis[11][11],d[20][20],res; int ok(int x,int y) { if(x>=1&&x<=n&&y>=1&&y<=x) return 1; else return 0; } int dfs(int x,int y,int sym) // 计算 数字sym连通集合中该数字的个数 { vis[x][y]=1; int step=1; for(int i=0;i<6;i++) { int x1=x+mov[i][0]; int y1=y+mov[i][1]; if(ok(x1,y1)&&!vis[x1][y1]) { if(d[x1][y1]==sym) step+=dfs(x1,y1,sym); if(d[x1][y1]==0) flag=1; } } return step; } void solve() { res=-10000; for(int i=1;i<=n;i++)//枚举每一个可以放c的地方 for(int j=1;j<=i;j++) { if(d[i][j]==0) { int ans=0,tem; d[i][j]=c; memset(vis,0,sizeof(vis)); for(int k=1;k<=n;k++) for(int p=1;p<=k;p++) { if(vis[k][p]||d[k][p]==0) continue; flag=0; tem=dfs(k,p,d[k][p]); if(!flag) { if(d[k][p]==c) ans-=tem; else ans+=tem; } } d[i][j]=0; res=MAX(res,ans); } } } int main() { while(~scanf("%d%d",&n,&c)&&(n+c)) { for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) scanf("%d",&d[i][j]); solve(); printf("%d\n",res); } }
