POJ 1414 Life Line(搜索)

题意：

 

给定一块正三角形棋盘，然后给定一些棋子和空位，棋子序号为a（1<=a<=9)，group的定义是相邻序号一样的棋子。

然后到C（1<=N<=9）棋手在空位放上自己序号C的棋子， 放完后， 不与空位相邻的group被消去， 每消去一个不是C的棋子得一分， 消去C的棋子扣一分， 问能得到最多的分数是多少。

分析：

令ans = 0；

搜索每一个棋子， 找出他的group。

如果这个group不与空位相邻， 而且棋子与棋手序号相等， 那么ans -= group数量， 如果棋子不与棋手序号相等 ans += group数量

可以不设置全局变量来找出搜索块的数量

代码：

#include 
#include 
#include 
using namespace std;
const int maxn = 15;
int N, C;
int dir[6][2] = { {-1, 0},{-1, -1},{ 0, -1},{ 0, 1},{ 1, 0},{ 1, 1} };
bool vis[maxn][maxn];
int board[maxn][maxn];
bool conetZero = 0;
int dfs(int x, int y, int c)
{
    if(board[x][y] == 0)
    {
        conetZero = 1;
        return 0;
    }
    vis[x][y] = 1;
    int cnt = 1;
    for(int d = 0; d < 6; d++)
    {
        int tx = x, ty = y;
        tx += dir[d][0], ty += dir[d][1];
        if(tx <= 0 || tx > N || ty <= 0 || ty > tx || vis[tx][ty])
            continue;
        if(board[tx][ty] == c || board[tx][ty] == 0)
            cnt += dfs(tx,ty, c);
    }
    return cnt;
}
int solve()
{
    memset(vis, 0 , sizeof(vis));
    int ans = 0;

    for(int i = 1; i <= N; i++)
    for(int j = 1; j <= i; j++)
    {
        if(board[i][j] != 0 && !vis[i][j])
        {
            conetZero = 0;
            int temp = dfs(i,j,board[i][j]);
            if(!conetZero){
                ans += board[i][j] == C ? -temp: temp;
            }
        }
    }
    return ans;
}
int main()
{
    while(~scanf("%d %d", &N, &C) && N)
    {

        memset( board , 0 , sizeof(board) );

        for(int i = 1; i <= N; i++)
        for(int j = 1; j <= i; j++)
            scanf("%d", &board[i][j] );



        int ans = -123456;

        for(int i = 1; i <= N; i++)
        for(int j = 1; j <= i; j++)
        {
            if( board[i][j] == 0){
                board[i][j] = C;
                ans = max( ans, solve() );
                board[i][j] = 0;
            }
        }

        printf("%d
", ans);

    }
    return 0;
}