當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

NYOJ 195 飞翔

發(fā)布時(shí)間：2025/3/16 编程问答 24 豆豆

生活随笔收集整理的這篇文章主要介紹了 NYOJ 195 飞翔小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

飛翔

時(shí)間限制：3000?ms ?|? 內(nèi)存限制：65535?KB 難度：4 描述

鷹最驕傲的就是翱翔，但是鷹們互相都很嫉妒別的鷹比自己飛的快，更嫉妒其他的鷹比自己飛行的有技巧。于是，他們決定舉辦一場比賽，比賽的地方將在一個(gè)迷宮之中。

這些鷹的起始點(diǎn)被設(shè)在一個(gè)N*M矩陣的左下角map[1，1]的左下角。終點(diǎn)被設(shè)定在矩陣的右上角map[N,M]的右上角，有些map[i,j]是可以從中間穿越的。每一個(gè)方格的邊長都是100米。如圖所示：

沒有障礙，也沒有死路。這樣設(shè)計(jì)主要是為了高速飛行的鷹們不要發(fā)現(xiàn)死路來不及調(diào)整而發(fā)生意外。潘帕斯雄鷹冒著減RP的危險(xiǎn)從比賽承辦方戒備森嚴(yán)的基地中偷來了施工的地圖。但是問題也隨之而來，他必須在比賽開始之前把地圖的每一條路都搞清楚，從中找到一條到達(dá)終點(diǎn)最近的路。（哈哈，笨鳥不先飛也要拿冠軍）但是此鷹是前無古鷹，后無來鷹的吃菜長大的鷹--菜鳥。他自己沒有辦法得出最短的路徑，于是緊急之下找到了學(xué)OI的你，希望找到你的幫助。

輸入

本題有多組數(shù)據(jù)。以EOF為輸入結(jié)束的標(biāo)志。
每組測試數(shù)據(jù)的首行為n,m(0<n,m<=1000000),第2行為k（0<k<=1000）表示有多少個(gè)特殊的邊。以下k行為兩個(gè)數(shù)，i,j表示map[i,j]是可以直接穿越的。

輸出

僅一行，1，1-->n,m的最短路徑的長度，四舍五入保留到整數(shù)即可

樣例輸入

3 2

1 1

3 2

1 2

樣例輸出

383

AC碼：

#include<cstdio> #include<iostream> #include<algorithm> //#include<cstring> #include<cmath> using namespace std; struct node {int x;int y; }num[1001]; bool cmp(node p1,node p2) {if(p1.x==p2.x)return p1.y<p2.y;return p1.x<p2.x; } int Max(int a,int b) {return a>b?a:b; } int main() {int n=0,m=0,count[1001],i,j,max=0,k=0;while(scanf("%d%d",&n,&m)!=EOF){scanf("%d",&k);for(i=0;i<k;i++){scanf("%d%d",&num[i].x,&num[i].y);count[i]=1;}sort(num,num+k,cmp);max=0;for(i=k-2;i>=0;i--){for(j=i+1;j<k;j++){if(num[i].x<num[j].x&&num[i].y<num[j].y)count[i]=Max(count[i],count[j]+1);if(count[i]>max)max=count[i];}}double sum;sum=(n+m-2*max+sqrt(2)*max)*100;printf("%.0f\n",sum);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的NYOJ 195 飞翔的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

NYOJ

上一篇： NYOJ 171 聪明的kk
下一篇： Jeewx-Boot 1.2 小程序官网