poj 1414 dfs 搜索

本文主要是介绍poj 1414 dfs 搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给一个正三角形, 可以在任意一个 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;elsereturn 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;elseans+=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);}
}

这篇关于poj 1414 dfs 搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---