• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • 無人機航線規劃

    非最短非最長,因為只有10個點,直接搜

    標題:無人機航線規劃
    在這里插入圖片描述
    某海島遭遇颶風災害,道路設施受損嚴重。救援部門為盡快探明主要交通干道的受損情況,在地圖上劃定了主要交通干道的偵察點,
    (如圖a所示),決定使用無人機對這些偵察點進行偵察。救援部門想知道,在只有一架無人機,且無人機有航程限制的情況下,考慮
    無人機的返航,如何規劃無人機的航線(如圖b所示),才能對更多的偵察點進行偵察。

    給出無人機的起點0的坐標(x0,y0),偵察點的數量n, 無人機的航程m,以及各偵察點i的坐標(xi,yi)。

    請輸出覆蓋最多偵察點的路徑中航程最短的路徑。若路徑有多個,輸出字典序最大的路徑
    計算距離時請保留到小數點后兩位。

    【輸入格式】
    n m
    x0 y0
    x1 y1
    x2 y2
    . . .
    xn yn

    對于40%的數據,0<n<5;
    對于70%的數據,0<n<7;
    對于100%的數據, 0<n<10; 10<m<100; -10 <= xi, yi <= 10 ;

    【輸出格式】
    輸出無人機的偵察航線

    【輸入樣例1】
    5 35
    4 1
    2 7
    7 1
    0 8
    -3 -3
    3 6
    【輸出樣例1】
    0->4->3->1->5->2->0

    【輸入樣例2】
    10 45
    0 0
    9 -6
    -2 -5
    9 1
    9 9
    6 0
    -8 -7
    4 -2
    10 7
    -6 2
    -3 6
    【輸出樣例2】
    0->9->10->4->8->3->5->7->0

    資源約定:
    峰值內存消耗(含虛擬機) < 256M
    CPU消耗 < 2000ms

    請嚴格按要求輸出,不要畫蛇添足地打印類似:“請您輸入…” 的多余內容。

    所有代碼放在同一個源文件中,調試通過后,拷貝提交該源碼。
    不要使用package語句。不要使用jdk1.7及以上版本的特性。
    主類的名字必須是:Main,否則按無效代碼處理。
    在這里插入圖片描述
    錯誤10%是因為這個。。我不改。明明說了輸出字典序最大的路徑,哪里錯了。。倒過來

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    const double FIG=1e-2;
    int n,fnum=0,pt[15],fpt[15];
    bool f[15];
    double m,fm=0,x[15],y[15],dis[15][15];
    void Try(int num,int pos,double nowm)
    {
    	bool flag=0;
    	for(int i=n;i>0;i--)
    	{
    		if(!f[i]&&m-(dis[i][pos]+nowm+dis[i][0])>=FIG)
    		{
    			pt[num+1]=i;
    			f[i]=1;
    			Try(num+1,i,nowm+dis[i][pos]);
    			f[i]=0;
    			flag=1;
    		}
    	}
    	if(!flag)
    	{
    		if(num>fnum||num==fnum&&fm-(nowm+dis[pos][0])>FIG)
    		{
    			fnum=num;
    			fm=nowm+dis[pos][0];
    			for(int i=1;i<=num;i++)
    			{
    				fpt[i]=pt[i];
    			}
    		}
    	}
    }
    int main()
    {
    	scanf("%d%lf",&n,&m);
    	for(int i=0;i<=n;i++)
    	{
    		scanf("%lf%lf",&x[i],&y[i]);
    		for(int j=0;j<i;j++)
    		{
    			dis[i][j]=dis[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    		}
    		if(i)fm+=dis[i][i-1];
    	}
    	if(m-fm>=FIG)fnum=n;
    	Try(0,0,0);
    	for(int i=0;i<=fnum;i++)
    	{
    		printf("%d->",fpt[i]);
    	}
    	printf("0\n");
    	return 0;
    }
    
    版權聲明:本文為weixin_40367307原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/weixin_40367307/article/details/88426302

    智能推薦

    Linux C系統編程-線程互斥鎖(四)

    互斥鎖 互斥鎖也是屬于線程之間處理同步互斥方式,有上鎖/解鎖兩種狀態。 互斥鎖函數接口 1)初始化互斥鎖 pthread_mutex_init() man 3 pthread_mutex_init (找不到的情況下首先 sudo apt-get install glibc-doc sudo apt-get install manpages-posix-dev) 動態初始化 int pthread_...

    統計學習方法 - 樸素貝葉斯

    引入問題:一機器在良好狀態生產合格產品幾率是 90%,在故障狀態生產合格產品幾率是 30%,機器良好的概率是 75%。若一日第一件產品是合格品,那么此日機器良好的概率是多少。 貝葉斯模型 生成模型與判別模型 判別模型,即要判斷這個東西到底是哪一類,也就是要求y,那就用給定的x去預測。 生成模型,是要生成一個模型,那就是誰根據什么生成了模型,誰就是類別y,根據的內容就是x 以上述例子,判斷一個生產出...

    styled-components —— React 中的 CSS 最佳實踐

    https://zhuanlan.zhihu.com/p/29344146 Styled-components 是目前 React 樣式方案中最受關注的一種,它既具備了 css-in-js 的模塊化與參數化優點,又完全使用CSS的書寫習慣,不會引起額外的學習成本。本文是 styled-components 作者之一 Max Stoiber 所寫,首先總結了前端組件化樣式中的最佳實踐原則,然后在此基...

    基于TCP/IP的網絡聊天室用Java來實現

    基于TCP/IP的網絡聊天室實現 開發工具:eclipse 開發環境:jdk1.8 發送端 接收端 工具類 運行截圖...

    猜你喜歡

    19.vue中封裝echarts組件

    19.vue中封裝echarts組件 1.效果圖 2.echarts組件 3.使用組件 按照組件格式整理好數據格式 傳入組件 home.vue 4.接口返回數據格式...

    劍指Offer39-調整數組順序使奇數位于偶數前面

    一開始想著用冒泡排序的方法來做,但是bug還是很多,后來看了評論區答案,發現直接空間換時間是最簡單的,而且和快排的寫法是類似的。...

    【一只蒟蒻的刷題歷程】【藍橋杯】歷屆試題 九宮重排 (八數碼問題:BFS+集合set)

    資源限制 時間限制:1.0s 內存限制:256.0MB 問題描述 如下面第一個圖的九宮格中,放著 1~8 的數字卡片,還有一個格子空著。與空格子相鄰的格子中的卡片可以移動到空格中。經過若干次移動,可以形成第二個圖所示的局面。 我們把第一個圖的局面記為:12345678. 把第二個圖的局面記為:123.46758 顯然是按從上到下,從左到右的順序記錄數字,空格記為句點。 本題目的任務是已知九宮的初態...

    dataV組件容器寬高發生變化后,組件不會自適應解決方法

    項目中需要大屏幕數據展示,于是使用了dataV組件,但是使用是發現拖動瀏覽器邊框,dataV組件顯示異常,如圖: 于是查了官網,官網的解釋如下:   于是按照官網的意思編寫代碼: 于是可以自適應了...

    CSS3干貨10:如何做一個板塊標題水平線左邊帶顏色效果

    很多網站在設計欄目標題的時候,喜歡用下劃線分開欄目標題和內容部分。 而且線條左邊的部分往往還有顏色,且這個顏色跟標題的文字長短保持一致。效果如圖所示: 這種效果其實很簡單。 我這里給大家推薦兩種方式: 假定我們的標題部分 HTML 結構如下: 方式一:利用下邊框。灰色部分是 h1 的下邊框,藍色部分是 span 標簽的下邊框。 h1 的高度為 40px,span 也設置它的高度為 40px。這樣,...

    精品国产乱码久久久久久蜜桃不卡