UVa 1603 破坏正方形

题意：有一个火柴棍组成的正方形网格，计算至少要拿走多少根火柴才能破坏所有正方形。

思路：从边长为1的正方形开始遍历，将正方形的边长和它的实际火柴数保存起来。之后dfs搜索。

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

const int maxn = 60;

int n, m,best,s;
int map[maxn],size[maxn],fullsize[maxn];
int contins[maxn][maxn];

int row_match(int x, int y)   //行
{
    return (2 * n + 1)*x + y;
}

int col_match(int x, int y)  //列
{
    return (2 * n + 1)*x + n + y;
}

int edges()  //计算火柴根数
{
    return 2*n*(n + 1);
}

void init()
{
    int ans;
    cin >> n >> m;
    //初始化网格
    for (int i = 0; i < edges(); i++)
        map[i] = 1;
    while (m--)
    {
        cin >> ans;
        map[ans - 1] = 0;
    }
    s = 0;  //s用来为正方形编号
    memset(contins, 0, sizeof(contins));
    for (int i = 1; i <= n;i++)  //正方形的边长，从1开始到n
    for (int x = 0; x <= n - i;x++) //正方形左上角的x坐标
    for (int y = 0; y <= n - i; y++) //正方形左上角的y坐标
    {
        size[s] = 0;
        fullsize[s] = 4 * i;  //第s个正方形的边长
        //cout << fullsize[s] << "*" << endl;
        for (int j = 0; j < i; j++)
        {
            int a = row_match(x, y + j);      
            int b = row_match(x + i, y + j);  
            int c = col_match(x + j, y);     
            int d = col_match(x + j, y + i);  
            contins[s][a] = 1;  //储存正方形的边
            contins[s][b] = 1;
            contins[s][c] = 1;
            contins[s][d] = 1;
            size[s] += map[a] + map[b] + map[c] + map[d];  
        }
        s++;
    }
}

int find_sqware()
{
    for (int i = 0; i < s;i++)
    if (fullsize[i] == size[i])     return i; //找到未被破坏的正方形
    return -1;
}

void dfs(int dep)
{
    if (dep >= best) return;
    int k = find_sqware();
    if (k == -1) //每个正方形都已经被破坏
    {
        best = dep;
        return;
    }
    for (int i = 0; i < edges(); i++)
    {
        if (contins[k][i])
        {
            for (int j = 0; j < s;j++)
            if (contins[j][i])    size[j]--;  //破坏，边的数量减少
            dfs(dep + 1);
            for (int j = 0; j < s;j++)  //回溯
            if (contins[j][i])  size[j]++;
        }
    }
}
int main()
{
    //freopen("D:\txt.txt", "r", stdin);
    int t;
    cin >> t;
    while (t--)
    {
        init();
        best = n*n;
        dfs(0);
        cout << best << endl;
    }
    return 0;
}

UVa 1603 破坏正方形

相关推荐