首页 > 试题广场 >

收集纸片

[编程题]收集纸片
  • 热度指数：1244 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
我们把房间按照笛卡尔坐标系进行建模之后，每个点就有了一个坐标。
假设现在房子里有些纸片需要被收集，收集完纸片你还要回归到原来的位置，你需要制定一个策略来使得自己行走的距离最短。
你只能沿着 x 轴或 y 轴方向移动，从位置 (i,j) 移动到相邻位置 (i+1,j)，(i-1,j)，(i,j+1) 或 (i,j-1) 距离增加 1。


输入描述:
在第一行中给出一个, 代表测试数据的组数。
对于每组输入，在第一行中给出房间大小，第二行给出你的初始位置。
接下来给出一个正整数  代表纸片的个数。
接下来 n 行，每行一个坐标代表纸片的位置。
保证房间小于 ，纸片一定位于房间内。


输出描述:
对于每组输入，在一行中输出答案。
格式参见样例。
示例1

输入

1
10 10
1 1
4
2 3
5 5
9 4
6 5

输出

The shortest path has length 24
算法知识视频讲解
开通博客
头像 RandolphJ
发表于 2020-02-25 13:33:46
一不小心拿了运行时间最快qwq（2ms）（截止此时） 要求从一个初始位置开始，经过所有的纸片，最终再回到初始坐标，求走过的最短距离。 方法1：暴力枚举或dfs（2ms） 我们可以用求1~n的全排列，计算所有可能的走法，由于纸片数不超过10，所以走法最多只有10!种。 全排列求法见《算法竞赛进阶指南》 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 此在Dasein
发表于 2025-11-17 01:00:24
这是一个典型的旅行商问题（TSP）变种，需要从起点出发，访问所有目标点（纸片）后返回起点，且只能沿坐标轴方向移动（曼哈顿距离）。由于纸片数量 ，数据规模很小，适合使用状态压缩动态规划（DP + Bitmask）进行精确求解。 核心观察： 两点间最短距离为曼哈顿距离： 访问顺序影响总距离，需要找到最 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 LoGic123456789
发表于 2020-05-19 23:07:11
这个题我觉得好难啊，不过A掉的人不少。我的想法就是类似最小生成树的prim算法，不过这里不再是找与已联通的点集相连的最小边，而是找与某点相连的最小边。这样，只需要找n-1次就可以找到一条将所有点连接起来的单向路径，然后按照题意加上终点到起点的距离就可以了。 #include <bits/std 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 sunrise__sunrise
发表于 2020-05-20 17:55:01
A、收集纸片 状态压缩dp ）当初小白赛可以过这道题，是因为前几天做过一题比较类似的小松鼠找松果的题目…… 回到这个题目，题目给出的地图很小最大也就是可以考虑二进制枚举。那么就开一个数组代表以为终点把二进制表示中的1走过一遍的最小花费。那么第一步预处理每两个点之间的距离，以及和源点之间的距离。初始化 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 Kato_Shoko
发表于 2025-11-17 10:36:37
数据很小，可以考虑直接暴力枚举所有的状态，然后暴力的走 #include <bits/stdc++.h> #define il inline using namespace std; using ll = long long; using ull = unsigned long lon 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 quchen666
发表于 2025-11-17 13:30:33
数据量很小，直接全排列枚举前往点的顺序,再按照path顺序遍历所有点求出答案，时间复杂度为O(n!*n); #include <bits/stdc++.h> using namespace std; int n; int sx,sy; int a[11],b[11]; vector< 展开全文
去ta的博客 赞 (1) 回复(1) 收起
头像 Ahui2667d
发表于 2025-11-17 21:04:16
dfs（捡起的纸片数量，当前所在位置） #include<bits/stdc++.h> using namespace std; int n, ans = 1e9; struct pos { int x; int y; } paper[20]; bool book[30]; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 czcczz
发表于 2025-11-17 21:11:10
#include<bits/stdc++.h> using namespace std; const int N=25; int mp[N][N]; int n; int minlen=0x3f3f3f3f; int res; int x,y; pair<int,int> p 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 19_hanhan
发表于 2020-05-21 13:16:09
题目 题目描述： 我们把房间按照笛卡尔坐标系进行建模之后，每个点就有了一个坐标。 假设现在房子里有些纸片需要被收集，收集完纸片你还要回归到原来的位置，你需要制定一个策略来使得自己行走的距离最短。 你只能沿着 x 轴或 y 轴方向移动，从位置 (i,j) 移动到相邻位置 (i+1,j)，(i-1 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 acuteQIQI
发表于 2025-11-17 21:50:52
#include <stdio.h> #include <stdlib.h> #include <limits.h> #define MAX_POINTS 12 // 起点 + 最多10个纸片 + 缓冲 #define INF INT_MAX typedef s 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

难度：
2条回答 6浏览

热门推荐

相关试题

收集纸片

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号