搜索

题意：先给出大方阵的边长，再给出m个小方阵并给出每个方阵的边长，问是否可以不发生重叠地把小方阵放进大方阵中，并且大方阵完全利用没有剩余

这题的代码不难写，关键是要找到策略，这题的策略比搜索本身的剪枝更有价值

摆放小方阵的策略是，尽可能往上面摆，然后尽可能往左边摆。另外有个策略一开始想错了，我是想先把小方阵排序，先放好大的，再放好小的，这样在摆放过程中可能出问题，画图可知，正确的策略是就目前的摆放情况，能放得到下哪个就放哪个，无所谓大小

 

为了满足尽可能放在左上方的条件，需要记录大方针的状态

col[i]的意义是，第i列，从最顶部数下来，被连续占据了多少格

注意在整个摆放过程中，每一列都保证是被连续占据的，不会出现断开的情况，这要求在搜索剪枝的时候处理好

 

#include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 55#define M 15int n,m;int col[N],s[M];bool dfs(int mm){    if(mm >= m) return true;    int Min = N , c = 0;    for(int i=1; i<=n; i++)        if(col[i] < Min)        {            Min = col[i];            c = i;        }    for(int i=1; i<=10; i++)        if(s[i])        {            bool ok = true;            if( !(c+i-1 <= n && col[c]+i <= n) ) continue;            for(int k = c; k <= c+i-1; k++)                if(col[k] != col[c])                {                     ok = false;                     break;                 }            if(!ok) continue;                        s[i]--;            for(int k=c; k <= c+i-1; k++)                col[k] += i;            if(dfs(mm+1)) return true;            s[i]++;            for(int k=c; k <= c+i-1; k++)                col[k] -= i;        }    return false;}int main(){    int cas;    cin >> cas;    while(cas--)    {        int x,sum = 0;        cin >> n >> m;        memset(s,0,sizeof(s));        for(int i=0; i
        
         > x;            s[x]++;            sum += x * x;        }        memset(col,0,sizeof(col));        if(sum != n * n || !dfs(0)) cout << "HUTUTU!" << endl;        else                        cout << "KHOOOOB!" << endl;    }    return 0;}