蓝桥杯2019年第十届省赛真题-糖果

解题思路:
IDA*优化暴搜

其实IDA* 是由两部分组成，迭代加深＋估价函数。

迭代加深　其实就是在我们深搜的时候，为了防止DFS在一个错误的方向上一直延伸向下查找，而设立每一次搜索对搜索层数的限制，如果答案在更深层，则depth＋＋

估价函数　其实就是我们在深搜时进行的一个可行性剪枝，在这个题目里我们是进行对目标的预估，比如总的层数有５层，如果我们现在搜索到了第三层，现在预估函数给出我们至少还需要３层,则总的层数＜现在所在的层数　＋还剩的层数，则退出。

代码里面还有一些细节操作来说明一下，在一个每一行中，我们可以用０１来表示有没有糖果，所以我们可以利用二进制来存储，数据范围ｍ＜20，所以用int储存１＜＜ｍ是完全足够的。同时在搜索的时候，可以用lowbit取得最低位的１来优化。而且搜索过程中，我们可以找每列中最少的那一行，比如在案例中，４只有一行出现过，那么它就是必选的，而１在很多行都出现，所以我们的策略直接从最少的开始查找，进一步优化速度。

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 110, M = 1 << 20;

vector<int> col[N];

int Log2[M];

int n,m,k;

int lowbit(int x){return x & -x;}       //返回最低位的1所对应的值

bool h(int state)                           //可行性剪枝 /估价函数 

{

    int res = 0;

    for(int i = (1 << m) - 1 - state;i;i -= lowbit(i))

    {

        int c = Log2[lowbit(i)];

        res ++ ;

        for(auto row : col[c]){

            i &= ~row;                                    //因为i是反的，所以得先将row取反 

        }

    }

    return res;

}

bool dfs(int depth,int state)

{

    if(!depth || h(state) > depth) return state == (1 << m) - 1;         //如果层数搜完了，或者剪枝不够在继续 则返回状态stare 

    // 找到选择性最少的一列

    int t = -1;

    for(int i = (1 << m) - 1 - state; i;i -= lowbit(i))            //i这里将原本为 表示1作为有糖果，转化为0有糖果，这样可以让lowbit查找优化 

    {

        int c = Log2[lowbit(i)];

        if(t == -1 || col[t].size() > col[c].size() )

        {

            t = c;

        }

    }

    for(auto row : col[t])                                 //搜索下一层 

    {

        if(dfs(depth - 1,state | row)){

            return true;

        }

    }

    return false;

}

int main()

{

    cin >> n >> m >> k;

    for(int i = 0; i < m; i ++ ) Log2[1 << i] = i;

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

    {

        int state = 0;

        for(int j = 0; j < k ; j ++ )

        {

            int c;

            cin >> c;

            state |= 1 << c - 1;

        }

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

            if(state >> j & 1)

            {

                col[j].push_back(state);

            }

    }

    int depth = 0;                       

    while(depth <= m && !dfs(depth,0)) depth ++ ; //IDA*迭代加深  搜索一层情况，不够在慢慢扩散 

    if (depth > m) depth = -1;

    cout<<depth<<endl;

    return 0;

}