当前位置：首页 > ds >正文

洛谷题解 | CF111C Petya and Spiders

ds 2025/5/2 1:44:15

题目描述

Little Petya loves training spiders. Petya has a board $ n×m $ in size. Each cell of the board initially has a spider sitting on it. After one second Petya chooses a certain action for each spider, and all of them humbly perform its commands. There are 5 possible commands: to stay idle or to move from current cell to some of the four side-neighboring cells (that is, one command for each of the four possible directions). Petya gives the commands so that no spider leaves the field. It is allowed for spiders to pass through each other when they crawl towards each other in opposite directions. All spiders crawl simultaneously and several spiders may end up in one cell. Petya wants to know the maximum possible number of spider-free cells after one second.

输入格式

The first line contains two space-separated integers $ n $ and $ m $ ( $ 1<=n,m<=40,n·m<=40 $ ) — the board sizes.

输出格式

In the first line print the maximum number of cells without spiders.

输入输出样例 #1

输入 #1

1 1

输出 #1

输入输出样例 #2

输入 #2

2 3

输出 #2

说明/提示

In the first sample the only possible answer is:

In the second sample one of the possible solutions is:

 rdl rul s denotes command “stay idle”, l, r, d, u denote commands “crawl left”, “crawl right”, “crawl down”, “crawl up”, correspondingly.

题目简化

求在一个地图上放置障碍物的最小数量，使得所有空白格子都能被覆盖到。

题目思路

搜索。

首先遍历棋盘找到第一个没有蜘蛛的格子，如果找不到这样的格子，则更新最优解为当前留空格子数量 $x$ 。

对于没有蜘蛛的格子，尝试在其周围放置蜘蛛，调用搜索函数，更新留空格子数量 $x$ ，直到所有格子都被蜘蛛占满或者当前留空格子数量 $\ge$ 最优解（也就是说一定是最优解法）时终止。

在尝试放置蜘蛛后，恢复棋盘。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n,m,best,dx[5] = {0,1,0,-1,0},dy[5] = {-1,0,1,0,0},a[45][45];
///判断坐标是否在棋盘范围内
bool ok(int x,int y){return x >= 0 && x < n && y >= 0 && y < m;
}
void dfs(int x){vector<pair<int,int> > tmp;int xx = -1,yy = -1;//寻找没有蜘蛛的格子for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(!a[i][j]){xx = i,yy = j;break;}}if(xx != -1) break;}//没有找到if(xx == -1){best = x;return;}if(x + 1 >= best) return;for(int i = 0;i < 5;i++){//尝试在空格子周围放置蜘蛛int x1 = xx + dx[i];int y1 = yy + dy[i];if(ok(x1,y1)){tmp.clear();for(int j = 0;j < 5;j++){//遍历当前位置(x1, y1)周围的五个点int x2 = x1 + dx[j];int y2 = y1 + dy[j];if(ok(x2,y2) && !a[x2][y2]){ //判断该点是否在棋盘范围内且没有蜘蛛tmp.push_back(make_pair(x2,y2)); //保存当前可以放置蜘蛛的位置a[x2][y2] = 1; //将蜘蛛标记为已占据}}dfs(x + 1); //搜索下一个没有蜘蛛的位置for(int j = 0;j < tmp.size();j++) a[tmp[j].first][tmp[j].second] = 0; //恢复之前放置蜘蛛后的状态}}
}
int main()
{cin >> n >> m;best = n * m;dfs(0);cout << n * m - best;return 0;
}