1411.txt

来自「自己AC的zju_acm上的若干个题目,都是自己辛辛苦苦AC的。」· 文本 代码 · 共 99 行

#include <iostream> 
#include <string> 
using namespace std; 

const int MAX = 30; 
const int MAX_SIDE = 11; 

int side[MAX_SIDE]; 
int S, N; 

inline bool IsValid(int r, int c) 
{ 
    return (r >= 0 && r < S && c >= 0 && c < S); 
} 

inline bool Fill(int r, int c, int si, bool cake[MAX][MAX]) 
{ 
    for (int r1 = 0; r1 < si; ++r1) { 
        for (int c1 = 0; c1 < si; ++c1) { 
            if ( !IsValid(r1 + r, c1 + c) ) return false; 
            if (cake[r1 + r][c1 + c] == true) { 
                return false; 
            } 
            cake[r1 + r][c1 + c] = true; 
        } 
    } 
    return true; 
} 

inline void GetEmpty(int &r, int &c, bool cake[MAX][MAX]) 
{ 
    for (r = 0; r < S; ++r) { 
        for (c = 0; c < S; ++c) { 
            if (cake[r][c] == false) { 
                return; 
            } 
        } 
    } 
} 

bool Search(bool cake[MAX][MAX]) 
{ 
    int r, c; 
    GetEmpty(r, c, cake); 

    if (r == S && c == S) return true; 

    bool cur[MAX][MAX]; 
    for (int i = 1; i < MAX_SIDE; ++i) { 
        if (side[i] > 0) { 
            memcpy(cur, cake, sizeof(cur)); 
            if ( !Fill(r, c, i, cur) ) { 
                continue; 
            } 
            // 
            side[i]--; 
            if ( Search(cur) ) return true; 
            side[i]++; 
        } 
    } 
    return false; 
} 

void Solve() 
{ 
    bool cake[MAX][MAX]; 
    memset(cake, 0, sizeof(cake)); 
    
    if ( Search(cake) ) { 
        cout << "KHOOOOB!\n"; 
    } 
    else { 
        cout << "HUTUTU!\n"; 
    } 
} 

int main() 
{ 
    int cases; 
    cin >> cases; 
    for (int k = 0; k < cases; ++k) 
    { 
        cin >> S >> N; 

        memset(side, 0, sizeof(side)); 

        int sidelen; 
        for (int i = 0; i < N; ++i) { 
            cin >> sidelen; 
            side[sidelen]++; 
        } 
        
        Solve(); 
        
    } 
    
    return 0; 
}