题解：CF111C Petya and Spiders

· · 题解

CF111C Petya and Spiders 题解

大致思路：

我们可以看到 n × m ≤ 40，显然我们可以推算出 \max(n, m) ≤ 6，竟然只有 6，那我们搜索就行了。我们用 x 记录目前的有蜘蛛位置的数量，也就是聚集点，用 STL 维护回溯即可。

代码实现：

#include <bits/stdc++.h>
using namespace std;
#define LLL __int128_t
#define LL long long
#define uint unsigned;
#define ull unsigned LL;
#define qi std::queue < int >;
#define vi std::vector < int >;
#define pii std::pair < int, int >;
#define lowbit(x) ((x) & -(x))
#define pq std::priority_queue
#define ve std::vector < pair < int, int> >
#define pr std::priority_queue < int, int >
#define pri std::priority_queue<pair<int,int> ,vector<pair<int,int> > ,greater<pair<int,int> > >
#define qcin std::ios::sync_with_stdio(0)
#define pb push_back
#define me(a, b) std::memset(a, b, sizeof(a))

const double TLS = 1;
const double eps = 1e-9;
const int inf = 1 << 29;
const int CPS = CLOCKS_PER_SEC;
const int INF = 1 << 30;//设置一个边界
const double TLC = TLS * 0.97 * CPS;
const int N = 2e4 + 10;
const int MOD = 1e8 + 7;
void print(int x) {
    if (!x)
        return;

    print(x / 10);
    std::putchar(x % 10 + '0');
}
int n, m, mp[50][50], res;
int sx[] = {-1, 1, 0, 0, 0};
int sy[] = {0, 0, -1, 1, 0};
bool f = 0;
void dfs(int x)
{
    int A, B;
    f = 0;//判断变量初始化 
    for (int i = 1;i <= n; ++ i)
    {
        for(int j = 1;j <= m; ++ j)
        {
            if(mp[i][j] == 1)//有蜘蛛 
            {
                A = i, B = j;
                f = 1;
                break;
            }
        }
        if(f) break;
    }
    if(!f)//无蜘蛛了 
    {
        res = min(res, x);//找保留最小值 
        return;
    }
    if(x >= res - 1) return;
    for(int i = 0;i < 5; ++ i)//遍历方向（偏移量） 
    {
        int nx = A + sx[i];
        int ny = B + sy[i];
        if(nx < 1 || nx > n || ny < 1 || ny > m) continue;//判边界 
        ve p;
        for(int j = 0;j < 5; ++j)//遍历目前点的五个方向 
        {
            int nnx = nx + sx[j];
            int nny = ny + sy[j];
            //if(nnx < 1 || nnx > n || nny < 1 || nny > m) continue;
            if(mp[nnx][nny] == 1)
            {
                mp[nnx][nny] = 0;
                p.pb(make_pair(nnx, nny));
            }
        }
        dfs(x + 1);//继续搜索 
        for(int j = 0;j < p.size(); ++ j)
        {
            mp[p[j].first][p[j].second] = 1;//利用pair回溯 
        }
    }
}

signed main(void) {
    cin >> n >> m;
    for(int i = 1;i <= n; ++ i)
    {
        for(int j = 1;j <= m; ++ j)
        {
            mp[i][j] = 1;//初始化 
        }
    }
    res = n * m;//保留全部 
    dfs(0);
    cout << n * m - res << "\n"; 
    return 0;
}

这样这道题目就完成啦！！！