hdu 5113（2014北京—搜索+剪枝）

题意：有N*M的棋盘，用K种颜色去染，要求相邻块不能同色。已知每种颜色要染的块数，问能不能染，如果能，输出任一种染法。

最开始dfs失败了- -，优先搜索一行，搜完后进入下一列，超时。本来以为搜索不行，看别人给的思路就是搜索+剪枝。
但是一直不知道该怎么剪，看了解题报告才发现，剩下的格子的数量+1必需是剩余最多种类棋子的两倍，否则必定会有相邻存在。
例如 3*3的空格中，一类棋子最多只能占5个、

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace std;

int num[20];

int tmap[10][10];

int n,m,k;

bool dfs(int x,int y)

{

    for(int i = 1; i <= k; i++)

         if((n*m-(m*(x-1)+y-1)+1)/2<num[i])

            return false;

    for(int i = 1; i <= k; i++)

    {

        bool flag = true;

        if(y - 1>= 1)

        {

            if(tmap[x][y-1] == i)

                flag = false;

        }

        if(x - 1>= 1)

        {

            if(tmap[x-1][y] == i)

                flag = false;

        }

        if(num[i] > 0 && flag)

        {

            tmap[x][y] = i;

            num[i]--;

            if(x == n && m == y)

                return true;

            if(y + 1 <= m)

            {

                if(dfs(x,y+1))

                    return true;

            }

            else

            {

                if(x + 1 <= n)

                    if(dfs(x+1,1))

                        return true;

            }

            num[i]++;

            tmap[x][y] = -1;

        }

    }

    return false;

}

int main()

{

    int T;

    scanf("%d",&T);

    int cas = 1;

    while(T--)

    {

        scanf("%d%d%d",&n,&m,&k);

        for(int i = 1; i <= k; i++)

            scanf("%d",&num[i]);

        memset(tmap,-1,sizeof(tmap));

        printf("Case #%d:\n",cas++);

        if(dfs(1,1))

        {

            printf("YES\n");

            for(int i=1; i<=n; i++)

            {

                for(int j=1; j<m; j++)

                    printf("%d ",tmap[i][j]);

                printf("%d\n",tmap[i][m]);

            }

        }

        else

            printf("NO\n");

    }

    return 0;

}

巴特西

hdu 5113（2014北京—搜索+剪枝）

最新文章

热门文章