收集纸片

[编程题]收集纸片

热度指数：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

输入

输出

The shortest path has length 24

算法知识视频讲解

Yui___

全排列做法

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

int main()
{
    int t = 0;
    std::cin>>t;
    while(t--)
    {
        int room_x = 0,room_y = 0;
        std::cin>>room_x>>room_y;

        int origin_x = 0,origin_y = 0;
        std::cin>>origin_x>>origin_y;

        int n = 0;
        std::cin>>n;
        std::vector<std::pair<int,int>> points(n);
        std::vector<int> index(n);
        for(int i = 0;i<n;++i)
        {
            index[i] = i;
            auto&[a,b] = points[i];
            std::cin>>a>>b;
        }

        int ans = 0x3f3f3f3f;

        do{
            int tmp_ans = 0;
            int cur_x = origin_x,cur_y = origin_y;
            for(int i = 0;i<n;++i)
            {
                auto&[a,b] = points[index[i]];
                tmp_ans+=(std::abs(a-cur_x)+std::abs(b-cur_y));

                cur_x = a;
                cur_y = b;
            }

            tmp_ans+=(std::abs(origin_x-cur_x)+std::abs(origin_y-cur_y));

            ans = std::min(ans,tmp_ans);

        }while(std::next_permutation(index.begin(),index.end()));
        
        std::cout<<"The shortest path has length "<<ans<<'\n';
    }
}

发表于 2025-11-17 18:50:05 回复(0)