题意:
一个游戏,题目很长讲的都是游戏规则,不难懂。
思路:
因为数据量小,直接暴力深搜即可。
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) using namespace std; const int N=15; const int inf=(1<<30); int n,m; int mat[N][N]; bool vis[N][N]; int mi[6]={0,-1,-1,0,1,1}; int mj[6]={-1,-1,0,1,1,0}; bool dfs(int i,int j) { vis[i][j]=true; for(int k=0;k<6;k++) { int ii=i+mi[k]; int jj=j+mj[k]; if(jj<=ii&&ii>=1&&jj>=1&&ii<=n&&!vis[ii][jj]) { if(!mat[ii][jj]) return true; if(mat[ii][jj]==mat[i][j]) { if(dfs(ii,jj)) return true; } } } vis[i][j]=false; return false; } void solve() { int ans=-inf; for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) { if(!mat[i][j])//找到为0的点,插入m值。 { int ret=0; mat[i][j]=m; for(int i2=1;i2<=n;i2++) for(int j2=1;j2<=i2;j2++) { if(mat[i2][j2]) { memset(vis,0,sizeof(vis)); if(mat[i2][j2]==m) ret-=!dfs(i2,j2); else ret+=!dfs(i2,j2); } } mat[i][j]=0; ans=Max(ans,ret); } } printf("%d\n",ans); } int main() { while(scanf("%d%d",&n,&m),n||m) { for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) { scanf("%d",mat[i]+j); } solve(); } return 0; }